树形DP

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n,K;
int dp[100005][3];      // subtree count for 3 colors
int cl[100005];         // -1 or 0-2
vector<int> adj[100005];
const int MOD = 1e9 + 7;
 
void dfs(int s, int e) {
    dp[s][0] = dp[s][1] = dp[s][2] = 1;
    for (int u: adj[s]) {
        if (u == e) continue;
        dfs(u, s);
    }
    for (int i = 0; i < 3; i++)
        for (int u: adj[s]) {
            if (u == e) continue;
            int sum = 0;
            for (int j = 0; j < 3; j++) {
                if (i == j) continue;
                sum = ((ll)sum + dp[u][j]) % MOD;
            }
            dp[s][i] = ((ll)dp[s][i] * sum) % MOD;  // multiply all children color combinations
        }
    for (int i = 0; i < 3; i++)
        if (cl[s] >= 0 && i != cl[s])       // apply current node color
            dp[s][i] = 0;
}
 
int main() {
    scanf("%d %d", &n, &K);
    for (int i = 0; i < n-1; i++) {
        int u,v;
        scanf("%d %d", &u, &v);
        u--,v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    fill(cl, cl+n, -1);
    for (int i = 0; i < K; i++) {
        int b,c;
        scanf("%d %d", &b, &c);
        cl[b-1] = c-1;
    }
    dfs(0, -1);
    printf("%lld", ((ll)dp[0][0] + dp[0][1] + dp[0][2]) % MOD);
 
    return 0;
}