http://codeforces.com/contest/1153/problem/D
给出一颗有根树，叶子节点可以从1开始赋值但不能相同，每个节点有一个属性max/min表示选择所有儿子值中的max/min作为自己的值，问根节点最大值。
考虑根的值如果是x，把>=x的值称为‘1‘，反之称为‘0‘，f[i]表示要想使得节点i为‘1‘的以i为根的子树中叶子节点为‘1‘的最小数量是多少。答案就是 |叶子节点|+1-f[1]。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 5 const int maxn=300005+15; 6 int in[maxn],op[maxn]; 7 int res=0,f[maxn]; 8 vector<int>g[maxn]; 9 void dfs(int u){ 10 if(u!=1 && in[u]==1){ 11 f[u]=1; 12 res++; 13 return; 14 } 15 if(op[u])f[u]=maxn; 16 else f[u]=0; 17 for(auto v:g[u]){ 18 dfs(v); 19 if(op[u]){ 20 f[u]=min(f[u],f[v]); 21 }else{ 22 f[u]+=f[v]; 23 } 24 } 25 } 26 int main(){ 27 int n,x; 28 cin>>n; 29 for(int i=1;i<=n;++i)cin>>op[i]; 30 for(int i=2;i<=n;++i){ 31 cin>>x; 32 in[x]++,in[i]++; 33 g[x].push_back(i); 34 } 35 dfs(1); 36 cout<<res+1-f[1]<<endl; 37 return 0; 38 }
原文：https://www.cnblogs.com/zzqc/p/10713562.html