CodeM 黑白树

题目描述：

一棵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变黑

输出描述:

一个数表示最少操作次数

输入例子1:

4 1 2 1 1 2 2 1

输出例子1:

3

看到这道题目不难想到DFS序和拓扑排序加贪心。

确实，要注意叶子节点只能自己给自己染色，被其他节点染色过的节点可以继续染色不影响结果。

例如先染叶子节点假设他的父亲节点已经被他染色了，但是这个时候父亲节点可以继续染色，相当于先染父亲再染儿子，

不影响结果。

然后进行一次DFS这个地方比较关键，我们要按DFS序处理问题。

1.先处理叶子节点（如果一个父节点他的左右子树全是黑色那么视为叶子节点），这个就是DFS序了，

2.如果该节点没有染色，那么在自己与儿子传来的k值中选取最大的进行染色，并且将它所能够染色的范围全部染色。

3.如果该节点已经被染色了，那么就把他的k-1传给他的父亲。

4.在把染色路径进行进行一个类似路径压缩的优化，这个过程不难实现，就是每个节点记录他的下一个白色节点的位置即可，

这个优化可以大大降低时间复杂度，因为并不能保证每次必然是正确的白色节点所以只是接近O(n)。如果这一步没看懂，

前面123步实现也能AC

#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; typedef struct node { int color; int k; int father; int nexwhi; int disroot; vector<int> child; }node; node mp[100005]; int n,ans; void init() { ans=0; mp[1].nexwhi=0; for(int i=1;i<=n;i++) { mp[i].color=0; mp[i].father=0; mp[i].child.clear(); } } int coloration(int pt,int loop) { if(pt==0||loop<=0) { return pt; } else { mp[pt].color=1; loop-=(mp[pt].disroot-mp[mp[pt].nexwhi].disroot); return mp[pt].nexwhi=coloration(mp[pt].nexwhi,loop); } } int dfs(int pt,int deep) { int Max=-1; mp[pt].disroot=deep; for(int i=0;i<mp[pt].child.size();i++) { Max=max(Max,dfs(mp[pt].child[i],deep+1)); } if(mp[pt].color==0) { ans++; int loop=max(mp[pt].k,Max); coloration(pt,loop); return 0; } else { return max(mp[pt].k,Max)-1; } } int main() { while(scanf("%d",&n)==1) { init(); for(int i=2;i<=n;i++) { int mo; scanf("%d",&mo); mp[i].father=mo; mp[i].nexwhi=mo; mp[mo].child.push_back(i); } for(int i=1;i<=n;i++) { scanf("%d",&mp[i].k); } dfs(1,0); printf("%d\n",ans); } return 0; } 。