【每日一题】黑白树

黑白树

思路：

1.当一个点没有被下方已经选了的点覆盖到的时候，我们选择一个它或者它下方的能向上覆盖的最远的点。
2.另外，其实我们也并不关心这个点选的哪个，只需要知道往上能覆盖多远就行了，这个值其实可以直接维护到k数组里面，实际操作就是：
首先处理的一定是叶子结点y，它的k值就是题目输入的值，它父亲结点x的k值就需要维护了，具体的值为k[x]=max(k[x],k[y]-1),也就是两者求并集，k[y]-1是因为y到x的距离为1；
也就是说k[x]此时的作用是存结点x的子树中的结点(包括它自己)向上覆盖的最远距离。
3.f[x]数组表示存放已选结点可以从x结点往上覆盖f[x]-1个结点，当f[x]=0时表示已选结点不能覆盖x结点，需要取一个结点(但是上面说过了，我们不关心这个点选那个)，那怎么取呢，f[x]=k[x]就可以了，这个结点可能是自己也可能是儿子结点，f[x]的维护也和k数组一样。

代码：

#include <bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int n,ans,k[100005],f[100005];
vector<int>g[100005];
void dfs(int x,int fa) {
    for(int i=0;i<g[x].size();++i) {
        int y=g[x][i];
        dfs(y,x);        //到达叶子结点才开始下面的维护
        f[x]=max(f[x],f[y]-1);
        k[x]=max(k[x],k[y]-1);
    }
    if(!f[x]) {    //当到达叶子结点或者已选结点不能覆盖结点x时执行 
        ++ans;
        f[x]=k[x];
    }
}
int main() {
    js;
    cin>>n;
    for(int i=2;i<=n;++i) {
        int x;
        cin>>x;
        g[x].push_back(i);
    }
    for(int i=1;i<=n;++i)    cin>>k[i];
    dfs(1,0);    //从根节点开始往下搜 
    cout<<ans<<endl;
    return 0;
}