黑白树
黑白树
https://ac.nowcoder.com/acm/contest/7/B
此题解与官方题解大概相差不大，甚至代码都大同小异？？？但也是个人理解，望能帮到你。
为了方便描述，我们先来考虑最简单的树，如图，每个节点最多只有一个子节点。
对于这个图我们要怎么染色使得最少呢？
由于每个节点只能由自己染色或由其子节点染色来影响它变成黑色，故显然叶子节点必然要染色。
即给8染上黑色。
现在我们从下往上考虑，设表示从底下往上考虑到第i点时的最少染色数（且保证同染色数最优），最优即越往上影响越多即越优。
现在，，且对8进行染色。这时候
都黑了。
现在，到了节点 ,查看一下，已经被染了，所以此时
,且
都黑了
现在，到了节点,查看一下，没有被染，此时就必须多染一个点，（也许你想调整一下前面的染色？？但别忘了，我们cnt的染色方案已经给定位同染色数的最优了），所以如果发现还是白色就必须多染一个点，那为了满足往上染的最多，我们就必须从底部开始选选一个没染色的且往上最多的（这个最多是相对于节点
的位置的），有
和
两个点可以选择，那么自然是选择
了，所以
此时
都黑了。
显然且同样
都是黑***r>现在来到了节点
,同样必须选一个点来染色，即
纵观没有染色的（事实上不用分那么多，因为已经染色的没有让节点
变黑，所以这些不可能是往上染色最高的）有节点
都没有染色，看图，很显然给
染色是最好的，因为染了它，直接就可以上到最高点
了,此时
全都变黑了，任务已经结束了。
所以，你发现贪心策略了吗？
如果能被已经染色的点涂黑，那自然不改变染色。
如果不能，则要从前面找一个染色范围最大的点来染色。
更一般的，对于任意树。
叶子节点一定要染色。
然后从底部往上考虑：若节点已经被染色了，则维持现状。
若节点没被染色，则要从其子节点中找往上覆盖最大范围的点染色，并且更新该节点的最大染色范围。
此过程可以又dfs递归一下便可
代码：
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int N=1e5+7;
using namespace std;
vector<int>G[N];
int u[N],k[N],cnt;
void dfs(int x)
{
for(int y:G[x])
{
dfs(y);
u[x]=max(u[x],u[y]-1);//更新到该节点已染色的点的影响范围。
k[x]=max(k[x],k[y]-1);//更新到该节点的影响范围，即往上可以影响多少个，显然比起子节点少一。
}
if(!u[x])//该节点没法被已染色的点影响成黑色，必须多染一个点。
{
cnt++;
u[x]=k[x];//更新该节点的影响范围。
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
int n;
cin>>n;
rep(i,2,n)
{
int x;
cin>>x;
G[x].emplace_back(i);
}
rep(i,1,n)cin>>k[i];
dfs(1);
cout<<cnt<<endl;
}
查看20道真题和解析