洛谷题目传送门
题目描述
Farmer John 有一个大农场，农场上有 N 个谷仓（1≤N≤100000），其中一些已经涂色，另一些尚未涂色。Farmer John 想要为这些剩余的谷仓涂色，使得所有谷仓都被涂色，但他只有三种可用的油漆颜色。此外，他的获奖奶牛 Bessie 如果发现两个直接相连的谷仓颜色相同，会感到困惑，因此他希望确保这种情况不会发生。
保证 NN 个谷仓之间的连接不会形成任何“环”。也就是说，任意两个谷仓之间最多只有一条连接路径。
Farmer John 有多少种方式可以为剩余的未涂色谷仓涂色？
输入格式
第一行包含两个整数 N 和 K（0≤K≤N），分别表示农场上的谷仓数量和已经涂色的谷仓数量。
接下来的 N−1 行每行包含两个整数 x 和 y（1≤x,y≤N,x≠y），描述直接连接谷仓 x 和 y 的路径。
接下来的 K 行每行包含两个整数 b 和 c（1≤b≤N， 1≤c≤3），表示谷仓 b 已经被涂成颜色 c。
输出格式
计算为剩余谷仓涂色的有效方式数量，模 1e9+7，要求任何两个直接相连的谷仓颜色不同。
输入输出样例
输入 #1
4 1 1 2 1 3 1 4 4 3
输出 #1
8
思路
显然是树状dp，我们令 dp[u][i] 为节点 u 染为 i 号颜色的的方案数
由定义得到
对于没有染色的点，染所有颜色的方案数都为 1
对于已经染色的点，除了染的颜色方案数为 1，其余方案数都为 0
Code
#include<bits/stdc++.h>
using namespace std;
const long long N=2e5+5,mod=1e9+7;
long long tot,h[N],ne[N],to[N],a[N],n,m,dp[N][3];
void add(long long u,long long v){tot++;to[tot]=v;ne[tot]=h[u];h[u]=tot;
}
void dfs(int u,int fa){for(int i=h[u];i;i=ne[i]){int v=to[i];if(v==fa)continue;dfs(v,u);dp[u][1]=dp[u][1]*((dp[v][2]+dp[v][3])%mod)%mod;//更新结果 dp[u][2]=dp[u][2]*((dp[v][1]+dp[v][3])%mod)%mod;dp[u][3]=dp[u][3]*((dp[v][1]+dp[v][2])%mod)%mod;}
}
int main(){cin>>n>>m;int x,y;for(int i=1;i<n;i++){cin>>x>>y;add(x,y);add(y,x);}for(int i=1;i<=n;i++)dp[i][1]=dp[i][2]=dp[i][3]=1;//初始化方案数 for(int i=1;i<=m;i++){cin>>x>>y;if(y==1)dp[x][2]=dp[x][3]=0;else if(y==2)dp[x][1]=dp[x][3]=0;else dp[x][1]=dp[x][2]=0;}dfs(1,0);cout<<(dp[1][1]+dp[1][2]+dp[1][3])%mod;//分类用加法，输出结果 return 0;
}
