Barn Painting

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_map>
#include <numeric>
#include <iomanip>
#include <regex>
using namespace std;
#define pii pair<int, int>
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
const int dl[2] = {1, -1};
const int MOD = 1e9 + 7;
const int MAX = 100005;

int n, k;
vector<int> v[MAX];
long long dp[MAX][3];
vector<int> child[MAX];
bool zero[MAX][3];

void make_tree(int cur, int par){
    for(auto nxt : v[cur]){
        if(nxt != par){
            child[cur].push_back(nxt);
            make_tree(nxt, cur);
        }
    }
    if(child[cur].size() == 0){
        for(int i = 0; i < 3; i++){
            if(dp[cur][i] != -1){
                dp[cur][i] = 1;
            }
        }
    }
}

long long DP(int cur, int color){
    if(zero[cur][color]){
        return dp[cur][color] = 0;
    }
    if(dp[cur][color] != -1){
        return dp[cur][color];
    }
    dp[cur][color] = 1;
    for(auto nxt : child[cur]){
        long long tmp = 0;
        for(int i = 0; i < 3; i++) {
            if(i == color){
                continue;
            }
            tmp += DP(nxt,i);
            tmp %= MOD;
        }
        dp[cur][color] *= tmp;
        dp[cur][color] %= MOD;
    }
    return dp[cur][color];
}

int main() {
    FAST;
    freopen("barnpainting.in", "r", stdin);
    freopen("barnpainting.out", "w", stdout);
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 3; j++){
            dp[i][j] = -1;
        }
    }
    for(int x, y, i = 0; i < n - 1; i++){
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int x, color, i = 0; i < k; i++){
        cin >> x >> color;
        color--;
        for(int j = 0; j < 3; j++){
            if(j != color){
                zero[x][j] = true;
            }
        }
    }
    make_tree(1, -1);
    /*
    for(int i = 1; i <= n; i++){
        cout << i << ": ";
        for(auto x : child[i]){
            cout << x << " ";
        }
        cout << "\n";
    }
    */
    long long ans = 0;
    for(int i = 0; i < 3; i++){
        ans += DP(1, i);
        ans %= MOD;
    }
    cout << ans << "\n";

}

/*
4 1
1 2
1 3
1 4
4 3

 8
 */