题意： 给定一棵树，将树分成k个连通块，并且每个连通块内只有一个节点的方案数。 思路： 这个实在是想不出来啊，标解是开个dp[u][2]数组，表示只考虑u这颗子树并且u这个节点是否在有黑棋子的连通块中的方案数。 初始化就是如果黑色dp[u][1]=1,否则dp[u][0]=1; 转移也很骚： 枚举每个子树，由于乘法原理我们发现子树之间是相互独立的， dp[u][1]=dp[u][1](dp[j][0]+dp[j][1])+dp[u][0](dp[j][1]) dp[u][0]=dp[u][0]*(dp[j][0]+dp[j][1]) 为何这么转移？如果这个点已经被包括在有黑点的连通块中了，那么它儿子的子树有没有被包括都可以，由于是同一棵树那就用加法原理，但如果他之前没被包括，他可以通过与被包括黑棋子的子树相连。同理dp[u][0]的转移不再赘述。 AC代码：
#include<bits/stdc++.h> using namespace std; const int N=200010; int h[N]; int e[N*2]; int ne[N*2]; int idx; const int mod=1e9+7; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int n; int c[N]; long long dp[N][2]; void dfs(int u,int fa) { if(c[u]) dp[u][1]=1; else dp[u][0]=1; for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(j==fa) continue; dfs(j,u); dp[u][1]=(1ll*dp[u][1]*(dp[j][0]+dp[j][1])%mod+1ll*dp[u][0]*dp[j][1]%mod)%mod; dp[u][0]=dp[u][0]*(dp[j][0]+dp[j][1])%mod; } } int main() { memset(h,-1,sizeof h); cin>>n; for(int i=1;i<n;i++) { int x; cin>>x; add(i,x); add(x,i); } for(int i=0;i<n;i++) cin>>c[i]; dfs(0,-1); cout<<dp[0][1]<<endl; return 0; }