#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
const int N=100005;
vector<int> e[N];
int n,m,k,s,t;
ll f[N][3];
void dfs(int u,int fa){
	for (int &v:e[u]){
		if (v==fa) continue;
		dfs(v,u);
		f[u][0]=(f[u][0]*(f[v][1]+f[v][2]))%mod;
		f[u][1]=(f[u][1]*(f[v][0]+f[v][2]))%mod;
		f[u][2]=(f[u][2]*(f[v][0]+f[v][1]))%mod;
	}
} 
int main()
{
	cin>>n>>m;
	for (int i=1;i<n;++i){
		cin>>s>>t;
		e[s].push_back(t);
		e[t].push_back(s);
	}
	for (int i=1;i<=n;++i) 
		f[i][0]=f[i][1]=f[i][2]=1;
	for (int i=1;i<=m;++i){
		cin>>s>>t;--t;
		for (int j=0;j<=2;++j)
			if (j!=t) f[s][j]=0;
	}
	dfs(1,0);
	ll ans=(f[1][0]+f[1][1]+f[1][2])%mod;
	cout<<ans;
}

水题一道

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9+7;
const int N = 100010;
int n,k;
long long f[5][N];
vector<int> e[N];
bool vis[N];

void dfs(int u,int fa)
{
	long long ans1=1,ans2=1,ans3=1;
	for(int i=0 ; i < e[u].size() ; i++) 
	{
		int v = e[u][i];
		if(fa == v)
		    continue;
		dfs(v,u);
		ans1 =  ans1 * (f[2][v] + f[3][v]) % MOD;
		ans2 =  ans2 * (f[1][v] + f[3][v]) % MOD;
		ans3 =  ans3 * (f[1][v] + f[2][v]) % MOD;
	}
	if(vis[u])
	{
		f[1][u] = f[1][u] * ans1;
		f[2][u] = f[2][u] * ans2;
		f[3][u] = f[3][u] * ans3; 
	}
	else
	{
		f[1][u] = ans1 % MOD;
		f[2][u] = ans2 % MOD;
		f[3][u] = ans3 % MOD;
	}
	
} 
int main()
{
	cin >> n >> k;
	for(int i=1; i <= n-1; i++)
	{
		int u,v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u); 
	}
	for(int i=1; i <= k; i++)
	{
		int x,id;
		cin >> x >> id;
		f[id][x] = 1;
		vis[x] = 1;
	}
	dfs(1,0);
	cout << (f[1][1] + f[2][1] + f[3][1]) % MOD;
}

#include<bits/stdc++.h>
#define maxn 200005
#define ll long long
using namespace std;
const int TT=1e9+7;
int n,x,y,lnk[maxn],nxt[maxn],son[maxn],tot,m;
ll f[maxn][3];
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-f;ch=getchar();}
	while (ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
inline void add(int x,int y){nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y;}
inline void Dfs(int x,int fa){
	for (int i=0;i<3;i++){
		if (f[x][i]){for (int j=0;j<i;j++) f[x][j]=0;break;}
		f[x][i]=1;
	}
	for (int i=lnk[x];i;i=nxt[i])
	  if (son[i]!=fa){
	  	Dfs(son[i],x);
	  	f[x][0]=f[x][0]*((f[son[i]][1]+f[son[i]][2])%TT)%TT;
                f[x][1]=f[x][1]*((f[son[i]][0]+f[son[i]][2])%TT)%TT;
                f[x][2]=f[x][2]*((f[son[i]][1]+f[son[i]][0])%TT)%TT;
	  }
}
int main(){
	n=read(),m=read();
	for (int i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);
	for (int i=1;i<=m;i++) x=read(),y=read()-1,f[x][y]=1;
	Dfs(1,0);
	printf("%lld",(f[1][0]+f[1][1]+f[1][2])%TT);
	return 0V0;
}

一道很好的树形dp 但是我写了好久 一直改来改去的 还是对树形dp不是很熟练 不过还好最后A了

很容易想到dp[i,1/2/3] 表示 以i为根节点的染色方案数 1/2/3表示根节点染的颜色

转移方式：

dp[u][3]=dp[u][3]*(dp[to][1]+dp[to][2])%mod;
		
dp[u][2]=dp[u][2]*(dp[to][1]+dp[to][3])%mod;
		
dp[u][1]=dp[u][1]*(dp[to][2]+dp[to][3])%mod;

初始化：如果该点已经被染色成x了，dp[u,x]=1,剩余两个颜色设为0

如果该节点没有被染色 那么dp[u,1]=dp[u,2]=dp[u,3]=1

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int mod=1e9+7;
ll dp[maxn][4];
int val[maxn];
vector<int>Q[maxn];
int n,k;
void dfs(int,int);
int main(){
	cin>>n>>k;
	for(int i=2;i<=n;i++){
		int aa,bb;
		cin>>aa>>bb;
		Q[aa].push_back(bb);
		Q[bb].push_back(aa);
	}
	for(int i=1;i<=k;i++){
		int id;cin>>id;
		cin>>val[id];
	}
	dfs(1,1);
	cout<<(dp[1][1]+dp[1][2]+dp[1][3])%mod<<endl;
     return 0;
}
void dfs(int u,int fa){
	if(val[u]==1)
		dp[u][1]=1,dp[u][2]=dp[u][3]=0;
	else if(val[u]==2)
	    dp[u][2]=1,dp[u][1]=dp[u][3]=0;
	else if(val[u]==3)
	    dp[u][3]=1,dp[u][1]=dp[u][2]=0;
	else dp[u][1]=dp[u][2]=dp[u][3]=1;
	for(int i=0;i<Q[u].size();i++){
		int to=Q[u][i];
		if(to==fa)continue;
		dfs(to,u);
		dp[u][3]=dp[u][3]*(dp[to][1]+dp[to][2])%mod;
		dp[u][2]=dp[u][2]*(dp[to][1]+dp[to][3])%mod;
		dp[u][1]=dp[u][1]*(dp[to][2]+dp[to][3])%mod;
	}

}

欸嘿,不会有人以为我会直接把答案放上来吧,我删了几句