Barn Painting(树形dp)

Barn Painting

思路

简单的树形$dp$，标记已经涂好色的点就行了。

---

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int vis[N],dp[N][4],n,k;
vector<int>e[N];
void dfs(int u,int fa){
    if(vis[u]) dp[u][vis[u]]=1;
    else dp[u][1]=dp[u][2]=dp[u][3]=1;
    for(int v:e[u]){
        if(v==fa) continue;
        dfs(v,u);
        dp[u][1]=1LL*dp[u][1]*(dp[v][2]+dp[v][3])%mod;
        dp[u][2]=1LL*dp[u][2]*(dp[v][1]+dp[v][3])%mod;
        dp[u][3]=1LL*dp[u][3]*(dp[v][1]+dp[v][2])%mod;
    }
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),e[u].pb(v),e[v].pb(u);
    for(int i=1,u,v;i<=k;i++) scanf("%d%d",&u,&v),vis[u]=v;dfs(1,0);
    printf("%d\n",1LL*(dp[1][1]+dp[1][2]+dp[1][3])%mod);
    return 0;
}