NC 13249. 黑白树

链接

https://ac.nowcoder.com/acm/problem/13249

题意

有一颗树，开始时每个节点都是白色，每个节点 $i$ 可以将 $i$ 到根的链上（包括 $i$ 与根）所有与 $i$ 距离小于 $k[i]$ 的点变黑，问最少操作几次能把整棵树变黑

思路

我们考虑每次操作的起始节点 $x$ 与能够染色的最远的那个节点 $y$ 之间的这些节点如何操作

易得最优操作是找到 $fa[x]$ 与 $y$ 之间的节点能染色到最远的那个节点，这个节点就是下次操作的起始位置

考虑如何维护

设 $f[i]$ 为从 $i$ 点开始往上还有多少节点已经被染色:

$f[i]=max(f[i],f[j]-1)(j \in son(i))$

我们还要维护子树上的节点如果操作后能到达的最远点，我们可以利用 $k[i]$ 来维护：

$k[i]=max(k[i],k[j]-1)(j \in son(i))$

当 $f[i]=0$ 时，我们就要进行一次操作，我们并不需要知道操作的起始位置，操作后 $f[i]=k[i]$

代码

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=1e5+5;
vector<int>edge[N];
int res;
int k[N],f[N];
void dfs(int u) {
    for(auto v:edge[u]) {
        dfs(v);
        f[u]=max(f[u],f[v]-1);
        k[u]=max(k[u],k[v]-1);
    }
    if(!f[u]) res++,f[u]=k[u];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=2;i<=n;i++) {
        int a;
        cin>>a;
        edge[a].pb(i);
    }
    for(int i=1;i<=n;i++) cin>>k[i];
    dfs(1);
    cout<<res<<endl;
    return 0;
}