黑白树(13249)

Problem:

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

Solution:

将节点i涂成黑色,且节点i到根节点中小于k[i]距离的节点也会变成黑色。由此可以得出叶子节点是必须涂色的，所以我们可以从叶子节点开始涂色，在向上涂色的时候，如果遇到了叶子节点无法涂的节点j，那么我们就必须在节点j到叶子节点中再找一个可以向上延申涂色的节点进行涂色。因此，我们需要维护一个以当前节点为根的子树中，可以向上延申最远的一个距离，而遇到无法继续向上涂色的时候，就选取这个进行涂色，从而达到选取点最少。

// https://ac.nowcoder.com/acm/problem/13249
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define _for(i,s,t) for(int i=s;i<t;++i)
#define _rof(i,s,t) for(int i=s;i>t;--i)
#define rep(i,s,t) for(int i=s;i<=t;++i)
#define per(i,s,t) for(int i=s;i>=t;--i)
#define Ri(x) scanf("%d",&x)
#define Rii(x,y) scanf("%d%d",&x,&y)
#define INF 0x3f3f3f3f
using namespace std;
template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
typedef long long ll;
const int maxn = 1e5 + 10;
vector<int> v[maxn];
int ans;
int k[maxn],p[maxn];// p数组是标记当前的上色情况，p[i] = j,当j>0时代表的是i节点可以被上色，并且j的值代表的是还可以继续向上上色的距离 
void dfs(int nowp,int fa){
    _for(i,0,v[nowp].size()){
        int u = v[nowp][i];
        dfs(u,nowp);
        k[nowp] = max(k[nowp],k[u] - 1);// 更新nowp为根子树中能向上延申的最大距离（注意！！！向上延申距离是指子树中所有的点除去到nowp的距离还能继续延申的距离） 
        p[nowp] = max(p[nowp],p[u] - 1);// 更新nowp节点可以继续向上上色的最大距离 
    }
    if(!p[nowp]){ // 表示不能继续向上上色了 ，所以需要找到一个最大向上延申的点进行上色 
        ++ans;
        p[nowp] = k[nowp];
    }
}
int main(){
    IOS;
    int n,x;
    cin>>n;
    rep(i,2,n){
        cin>>x;
        v[x].push_back(i);
    }
    rep(i,1,n){
        cin>>k[i];
    }
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}
/**
Problem:
一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。
每个点都有一个颜色，初始的时候所有点都是白色的。你需要通过一系列操作使得最终每个点变成黑色。
每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑，
已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。

Solution:
将节点i涂成黑色,且节点i到根节点中小于k[i]距离的节点也会变成黑色。由此可以得出叶子节点是必须涂色的，
所以我们可以从叶子节点开始涂色，在向上涂色的时候，如果遇到了叶子节点无法涂的节点j，
那么我们就必须在节点j到叶子节点中再找一个可以向上延申涂色的节点进行涂色。
因此，我们需要维护一个以当前节点为根的子树中，可以向上延申最远的一个距离，而遇到无法继续向上涂色的时候，
就选取这个进行涂色，从而达到选取点最少。 

*/