题目：http://codeforces.com/contest/1153/problem/D
题意:给你一棵树，每个节点有一个操作，0代表取子节点中最小的那个值，1代表取子节点中最大的值，叶子节点的话就是自己置一个值，有k个子节点，那么每个子节点的值范围
就是1-k,1-k只能用一次
思路：贪心不好取，我肯定是要排列完才知道当前的值是哪个，但是我可以知道当前节点应该是取子节点中排名第几的那个，从而推出根节点1的排名，然后再输出就行，因为是要从
子节点那里递归上来，所以我们采取树形dp
#include<bits/stdc++.h> #define mod 1000000007 #define maxn 300005 using namespace std; vector<int> mp[maxn]; int d[maxn]; int dp[maxn]; int n,z,num; void dfs(int x){ int mn=0,mx=-1; for(int i=0;i<mp[x].size();i++){ dfs(mp[x][i]); if(mx==-1) mx=dp[mp[x][i]]; //取最大值也就是取排名最小的那一位 else mx=min(mx,dp[mp[x][i]]); mn+=dp[mp[x][i]]; //最小值也就是取最小的那个值，要先计算出包含多少个叶子节点，然后计算 } if(mp[x].size()==0)//如果是叶子节点 { dp[x]=1;//叶子结点排名第一 num++; } else{ if(d[x]==0) dp[x]=mn; else dp[x]=mx; } } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>d[i]; for(int i=2;i<=n;i++){//建图 cin>>z; mp[z].push_back(i); } dfs(1); cout<<num-dp[1]+1; }