首页 > 代码库 > Codeforces Round #263 (Div. 1)
Codeforces Round #263 (Div. 1)
B.Appleman and Tree
题目大意。一棵树上的点有的是黑的有的是白的，然后他想断开一些边使得剩下的连通分量里每个连通分量有且仅有一个黑点，求方案数。
dp[u][0]表示以u为根的子树且u所在的连通分量没有黑点的方案数。
dp[u][1]表示以u为根的子树且u所在的连通分量有一个黑点的方案数。
更新节点u时，对于他的子树v，可以断开或不断开这条边<u,v>。
#include <cstdio>#include <algorithm>#include <cstring>using namespace std;#define maxn 100100const __int64 MOD=1000000007;struct Edge{ int to,next;}edge[maxn*5];int cnt,head[maxn];int color[maxn];void addedge(int u,int v){ ++cnt; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt;}__int64 dp[maxn][2];void dfs(int u,int f){ dp[u][1]=0;dp[u][0]=0; if (color[u]==0) dp[u][0]=1; else dp[u][1]=1; int k; for(k=head[u];k;k=edge[k].next) { int v=edge[k].to; if (v==f) continue; dfs(v,u); int a=dp[u][0],b=dp[u][1]; dp[u][0]=a*(dp[v][0]+dp[v][1])%MOD; dp[u][1]=b*(dp[v][0]+dp[v][1])+a*dp[v][1]; dp[u][1]%=MOD; }}int main(){ int n,i; scanf("%d",&n); memset(head,0,sizeof head); cnt=1; for(int i=0;i<n-1;i++) { int u; scanf("%d",&u); addedge(u,i+1); addedge(i+1,u); } for(i=0;i<n;i++) scanf("%d",&color[i]); dfs(0,-1); printf("%I64d\n",dp[0][1]);}
Codeforces Round #263 (Div. 1)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。