[编程题] 黑白树
时间限制：1秒
空间限制：32768K
一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。
你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。
你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。
输入描述:
第一行一个整数n (1 ≤ n ≤ 10^5) 接下来n-1行，每行一个整数，依次为2号点到n号点父亲的编号。 最后一行n个整数为k[i] (1 ≤ k[i] ≤ 10^5) 样例解释: 对节点3操作，导致节点2与节点3变黑 对节点4操作，导致节点4变黑 对节点1操作，导致节点1变黑
输出描述:
一个数表示最少操作次数
输入例子:
4 1 2 1 1 2 2 1
输出例子:
3
分析：DFS深搜+暴力写法，可以参考一下的啦！
其实就是一个DFS递归啊，
子树全变黑的最优解：sum1，
在最优解sum1下最多还能向上延伸的点数，sum2，
sum3是，子树下不被选择的点作为备选的点，最多还能向上延伸的点数！
下面给出AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N =166666; 4 typedef long long ll; 5 vector<ll> T[N]; 6 ll n,a[N]; 7 struct Tree 8 { 9 ll ans; 10 ll maxn; 11 ll Gmaxn; 12 }; 13 inline ll read() 14 { 15 ll x=0,f=1; 16 char ch=getchar(); 17 while(ch<'0'||ch>'9') 18 { 19 if(ch=='-') 20 f=-1; 21 ch=getchar(); 22 } 23 while(ch>='0'&&ch<='9') 24 { 25 x=x*10+ch-'0'; 26 ch=getchar(); 27 } 28 return x*f; 29 } 30 inline void write(ll x) 31 { 32 if(x<0) 33 { 34 putchar('-'); 35 x=-x; 36 } 37 if(x>9) 38 { 39 write(x/10); 40 } 41 putchar(x%10+'0'); 42 } 43 Tree DFS(ll xx,ll yy) 44 { 45 Tree ret={0,0,0}; 46 ll sum1=0,sum2=-1,sum3=-1; 47 for(ll i=0;i<T[xx].size();i++) 48 { 49 ll to=T[xx][i]; 50 if(to==yy) 51 continue; 52 ret=DFS(to,xx); 53 sum1+=ret.ans; 54 sum2=max(ret.maxn,sum2); 55 sum3=max(ret.Gmaxn,sum3); 56 } 57 if(sum2<=-1) 58 { 59 sum2=max(a[xx],sum3); 60 sum1+=1; 61 } 62 sum3=max(sum3,a[xx]); 63 ret.ans=sum1; 64 ret.maxn=sum2-1; 65 ret.Gmaxn=sum3-1; 66 return ret; 67 } 68 int main() 69 { 70 ll p; 71 n=read(); 72 for(ll i=1;i<=n-1;i++) 73 { 74 p=read(); 75 T[p].push_back(i+1); 76 } 77 for(ll i=1;i<=n;i++) 78 { 79 a[i]=read(); 80 a[i]--; 81 } 82 write(DFS(1,0).ans); 83 return 0; 84 }
![【蓝桥杯】[递归]母牛的故事](https://ucc.alicdn.com/pic/developer-ecology/2is4p5rpji74e_be870067c97c42ca9083c25b149faaa5.png?x-oss-process=image/resize,h_160,m_lfit)
