自动搬运

查看原文

来自洛谷，原作者为

	LlLlCc 背井离乡，忍辱负重

搬运于2025-08-24 21:56:19，当前版本为作者最后更新于2019-08-15 21:29:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

经典的树形DP，适合入门练手

进入正题：

• f[i][j]表示i这个点上色为j是方案数（从下往上/从子节点向父节点更新）

• 即对于所有初始节点，f[i][1],f[i][2],f[i][3]都为1

• 当某个节点被指定上色后，那么该节点另外两种颜色的方案数为0。

  列如:当点x被指定上色 2 时：f[x][1]=0,f[x][3]=0 (因为无法上色1和3）

• 对于每个节点，因为不能于子节点上色相同,即：

   f[x][0]=f[x][0]*(f[son[i]][1]+f[son[i]][2]);
   f[x][1]=f[x][1]*(f[son[i]][0]+f[son[i]][2]);
   f[x][2]=f[x][2]*(f[son[i]][1]+f[son[i]][0]);

• 最后，记得取模和开long long

代码参考：

#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 0;
}