链接
Click here to see the original question
题目描述
一棵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)
输出
一个数表示最少操作次数
代码
只要用两个数组,一个数组f维护已经选中的点中能够到达的最远位置,一个数组k维护已经遍历过的点中能到达的最远位置,每次f数组不够用了(值为0)了,就用k数组来更新f数组。
#include <bits/stdc++.h> #define FIO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; int n, k[100009], f[100009], ans; vector<int>po[100009]; void dfs(int cur) { int len = po[cur].size(); for(int i = 0; i < len; i++){ int child = po[cur][i]; dfs(child); k[cur] = max(k[cur], k[child] - 1);//记录能覆盖的最远距离, 为下一次选点作参考 f[cur] = max(f[cur], f[child] - 1);//记录已经选的点中能到达的最远距离 } if(f[cur] == 0){//子代中已经选的点都不能到达该位置 f[cur] = k[cur];//就根据我们维护的k数组来选择点 //至于选的究竟是哪一点,我们不知道,也不关心 //我们只知道选了这一点后能让更多的点变黑 ans++;//选的点数+1 } //如果没看太懂,可以自己举一个简单的例子推一遍 } int main() { FIO; cin>>n; int a; for(int i = 2; i <= n; i++){ cin>>a; po[a].push_back(i); } for(int i = 1; i <= n; i++){ cin>>k[i]; } dfs(1); cout<<ans<<endl; return 0; }