首页 > 代码库 > Evensgn 剪树枝
Evensgn 剪树枝
问题 A: Evensgn 剪树枝
时间限制: 1 Sec 内存限制: 128 MB题目描述
繁华中学有一棵苹果树。苹果树有 n 个节点（也就是苹果），n − 1 条边（也就
是树枝）。调皮的 Evensgn 爬到苹果树上。他发现这棵苹果树上的苹果有两种：一
种是黑苹果，一种是红苹果。Evensgn 想要剪掉 k 条树枝，将整棵树分成 k + 1 个
部分。他想要保证每个部分里面有且仅有一个黑苹果。请问他一共有多少种剪树枝
的方案？
输入
第一行一个数字 n，表示苹果树的节点（苹果）个数。
第二行一共 n − 1 个数字 p0, p1, p2, p3, ..., pn−2，pi 表示第 i + 1 个节点和 pi 节
点之间有一条边。注意，点的编号是 0 到 n − 1。
第三行一共 n 个数字 x0, x1, x2, x3, ..., xn−1。如果 xi 是 1，表示 i 号节点是黑
苹果；如果 xi 是 0，表示 i 号节点是红苹果。
输出
输出一个数字，表示总方案数。答案对 109 + 7 取模。
样例输入
样例输入 260 1 1 0 41 1 0 0 1 0样例输入 3100 1 2 1 4 4 4 0 80 0 0 1 0 1 1 0 0 1
样例输出
样例输出 12样例输出 21样例输出 327
提示
数据范围
对于 30% 的数据，1 ≤ n ≤ 10。
对于 60% 的数据，1 ≤ n ≤ 100。
对于 80% 的数据，1 ≤ n ≤ 1000。
对于 100% 的数据，1 ≤ n ≤ 105。
对于所有数据点，都有 0 ≤ pi ≤ n − 1，xi = 0 或 xi = 1。
特别地，60% 中、80% 中、100% 中各有一个点，树的形态是一条链
solution：
这题考试考得时候水了30分的链，正解是树规，想到了但是推了转移方程没推出来QAQ。
f[i][0][0]代表第i个点是否砍掉，以它为根的子树中有没有黑点。
叶子节点：
如果是白点 如果是黑点： f[u][1][1]=0; f[u][1][1]=1;
f[u][0][1]=0; f[u][0][1]=1;
f[u][1][0]=1; f[u][1][0]=0;
f[u][0][0]=1; f[u][0][0]=0;
至于转移方程吗，很恶心的玩意：
黑点：f[u][1][0]=0; f[u][0][0]=0;（这两种情况不成立，不管砍不砍以它为根的子树中一定有黑点）
f[u][1][1]=f[v][1][1]+f[v][0][0]的乘积（它被砍了子树中只能有它一个黑点，所以儿子中要么没有黑点[0][0]要么有黑点被砍了[1][1]）
f[u][0][1]不知道暂时赋值为f[u][1][1]
白点：f[u][1][0]这种情况对答案没有贡献设为0，因为它为白点子树仍为白点都不能割；
f[u][0][0]=f[v][1][1]+f[v][0][0]的乘积（它的子树中没有黑点，儿子中要么没有黑点[0][0]要么有黑点被砍了[1][1]）
f[u][1][1]=∑f[x][0][1]*（f[v][1][1]+f[v][0][0]），它为白以它为根的子树中有且只有一个黑点，则只有一个黑点儿子不被砍，其余儿子中要么没有黑点[0][0]要么有黑点被砍了[1][1]
最后答案为f[0][0][1]
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 #define mod 1000000007 7 #define int long long 8 int read() { 9 int s=0,f=1; 10 char ch=getchar(); 11 while(ch>‘9‘||ch<‘0‘) { 12 if(ch==‘-‘) { 13 f=-1; 14 } 15 ch=getchar(); 16 } 17 while(ch>=‘0‘&&ch<=‘9‘) { 18 s=(s<<1)+(s<<3)+(ch^48); 19 ch=getchar(); 20 } 21 return s*f; 22 } 23 long long f[100005][2][2]; 24 int r[100005],tot,n; 25 //哪一个点 是否砍掉 子树中是否有黑点 26 int col[100005],son[100005]; 27 struct node { 28 int to,next; 29 } c[400005]; 30 void add(int x,int y) { 31 c[tot]=(node) { 32 y,r[x] 33 }; 34 r[x]=tot++; 35 }/* 36 void dfs1(int u,int v) { 37 for(int i=r[u]; ~i; i=c[i].next) { 38 if(c[i].to==v) { 39 continue; 40 } 41 dfs1(c[i].to,u); 42 son[u]=1; 43 } 44 }*/ 45 void dfs1(int u,int v) { 46 for(int i=r[u]; ~i; i=c[i].next) { 47 if(c[i].to==v) { 48 continue; 49 } 50 dfs1(c[i].to,u); 51 son[u]=1; 52 } 53 } 54 inline void dfs(int u,int v) { 55 if(!son[u]) { 56 if(col[u]) { 57 f[u][1][1]=1; 58 f[u][0][1]=1; 59 f[u][1][0]=0; 60 f[u][0][0]=0; 61 } else { 62 f[u][1][1]=0; 63 f[u][0][1]=0; 64 f[u][1][0]=1; 65 f[u][0][0]=1; 66 } 67 return ; 68 } 69 for(int i=r[u]; ~i; i=c[i].next) { 70 if(c[i].to==v) { 71 continue; 72 } 73 dfs(c[i].to,u); 74 } 75 if(col[u]) { //黑点 76 f[u][1][0]=0; 77 f[u][0][0]=0; 78 int sum=1; 79 for(int i=r[u]; ~i; i=c[i].next) { 80 if(c[i].to==v) { 81 continue; 82 } 83 sum=sum*(f[c[i].to][0][0]+f[c[i].to][1][1])%mod; 84 } 85 f[u][0][1]+=sum; 86 f[u][1][1]+=sum; 87 } else { //白点 88 f[u][1][0]=0; 89 int sum=1; 90 for(int i=r[u]; ~i; i=c[i].next) { 91 if(c[i].to==v) { 92 continue; 93 } 94 sum=sum*(f[c[i].to][0][0]+f[c[i].to][1][1])%mod; 95 } 96 f[u][0][0]+=sum; 97 int ans=0; 98 sum=1; 99 for(int i=r[u]; ~i; i=c[i].next,sum=1) {100 if(c[i].to==v) {101 continue;102 }103 int ji=f[c[i].to][0][1];104 if(!ji) {105 continue;106 }107 for(int j=r[u]; ~j; j=c[j].next) {108 if(c[j].to==v||j==i) {109 continue;110 }111 sum=sum*(f[c[j].to][0][0]+f[c[j].to][1][1])%mod;112 }113 ans=(ans+ji*sum)%mod;114 }115 f[u][1][1]=ans%mod;116 f[u][0][1]=ans%mod;117 }118 }119 signed main() {120 //freopen("tree9.in","r",stdin);121 memset(r,-1,sizeof(r));122 n=read();123 for(int x,i=0; i<n-1; i++) {124 x=read();125 add(x,i+1);126 add(i+1,x);127 }128 for(int i=0; i<n; i++) {129 col[i]=read();130 }131 dfs1(0,-1);132 dfs(0,-1);133 cout<<f[0][0][1]%mod;134 return 0;135 }
Evensgn 剪树枝