[编程题] 黑白树

时间限制：1秒

空间限制：32768K

一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点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变黑

输出描述:

一个数表示最少操作次数

输入例子:

41211 2 2 1

输出例子:

3

题目链接：

分析：DFS深搜+暴力写法，可以参考一下的啦！

其实就是一个DFS递归啊，

子树全变黑的最优解：sum1，

在最优解sum1下最多还能向上延伸的点数，sum2，

sum3是，子树下不被选择的点作为备选的点，最多还能向上延伸的点数！

下面给出AC代码：

1 #include
      
        2 using namespace std; 3 const int N =166666; 4 typedef long long ll; 5 vector
       
         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