【每日一题】4月8日题目精讲 黑白树

试题链接

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format:%lld

题目描述

一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。
你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。

输入描述:

第一行一个整数n (1 ≤ n ≤ 10⁵) 接下来n-1行，每行一个整数，依次为2号点到n号点父亲的编号。 最后一行n个整数为k[i]
(1 ≤ k[i] ≤ 10⁵)

样例解释:
对节点3操作，导致节点2与节点3变黑 对节点4操作，导致节点4变黑 对节点1操作，导致节点1变黑

输出描述:

一个数表示最少操作次数

示例1
输入

4
1
2
1
1 2 2 1

输出

3

题解：
一开始以为是红黑树的姐妹黑白树。。
求出最少的操作，用dfs

我们要不断更新染色的最远距离，还要把子节点的染色范围更新的父亲节点
比如1->2->3-.>4->5->6->7
f[2]=5,f[3]=2
2节点就可以直接染色到6
操作完2之后，如果3就已经被染色了，如果3能染色的范围比fa[ 2 ]-1（因为2已经染色了本身，所以减一）还大，那染色范围可以更远
如果fa[3]<fa[2]-1，就把f3的最远距离更新到fa[2]-1
总结就是fa[fa]=max（ fa [ fa ] , fa [ son ] - 1 ）

因为染色都是从下向上的。如果一个节点没办法被它子树的节点染色，那这个节点的父亲节点也没办法将它染色，他只能自己染色了

代码：

#include<bits/stdc++.h>
#define forr(n) for(int i=1;i<=n;i++)
using namespace std;
const int maxn=100004;
int fa[maxn];
int sum;
vector<int>w[maxn];
int a[maxn];
void dfs(int x)
{
	for(int j=0;j<w[x].size();j++)
	{
		dfs(w[x][j]);
		fa[x]=max( fa[ w[x][j] ]-1 , fa[x] );
		a[x]=max( a[ w[x][j] ]-1 , a[x] );
	}
	if(fa[x]==0)
	{
		sum++;
		fa[x]=a[x];
	}
	
}
int main()
{
	int n,m;
	cin>>n;
	forr(n-1)
	{
		cin>>m;
		w[m].push_back(i+1);
	}
	forr(n)
	{
		cin>>a[i];
	}
	dfs(1);
	cout<<sum;
	return 0;
	
}