P4084 [USACO17DEC]Barn Painting G
还是一道很好的树形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
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=1e5+5;
const int mod=1e9+7;
ll dp[maxn][4];
int val[maxn];
vectorQ[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<