原题链接

题解

1.对于没有固定颜色的节点来说，每个节点只会有三种颜色，而这又是一棵树，树形dp由此而来
2.由相邻节点不同确定转移方程
3.即使有求模也可能要开long long

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
vector<ll> G[100005];
vector<ll> color(100005, 0);

inline void read(ll &x) {  
    x = 0;
    ll flag = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') flag = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48); 
        c = getchar();
    }
    x *= flag;
}

inline void write(ll x)
{
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9) 
        write(x / 10);
    putchar(x % 10 + '0');
}

void add(ll x, ll y)
{
    G[x].push_back(y);
    G[y].push_back(x);
}

vector<vector<ll>> sum(100005, vector<ll>(4, 0));//代表以当前节点为根节点且颜色为1/2/3的方案数

void ss(ll now, ll fa) //求出以now为根节点的树的方案数
{
    for(ll i = 0; i < G[now].size(); i++)
    {
        ll next = G[now][i];

        if(next == fa) continue;
        ss(next, now);
        
            sum[now][1] = sum[now][1] * (sum[next][2] + sum[next][3]) % mod;//当前节点的方案数等于子节点的方案数乘积
            sum[now][2] = sum[now][2] * (sum[next][1] + sum[next][3]) % mod;//对于有固定颜色的点而言，其他颜色的初始值为零
            sum[now][3] = sum[now][3] * (sum[next][2] + sum[next][1]) % mod;
  
    }
}

int main()
{
    ll n, k;
    read(n); read(k);

    for(ll i = 1; i < n; i++)
    {
        ll x, y;
        read(x); read(y);
        add(x, y);
    }

    for(ll i = 1; i <= k; i++)
    {
        ll x;
        read(x); read(color[x]);
    }

    for(ll i = 1; i <= n; i++)
    {
        if(!color[i])
            for(ll j = 1; j <= 3; j++) sum[i][j] = 1;
        else sum[i][color[i]] = 1;//初始化
    }
    ss(1, 0);

    write(((sum[1][1] + sum[1][2]) % mod + sum[1][3]) % mod);
    return 0;
}