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

 

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

链接：https://ac.nowcoder.com/acm/problem/13249
来源：牛客网

题目描述

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

输出

复制 
3
　　　　
　　叶子节点一定要染色，边界确定。维护三个变量f[u][0/1/2],一个是以当前节点为根的子树花费的最小染色次数，一个
是对已经染色的子节点点来说，最长的染色距离，还有一个就是对于所有子节点来说最长的染色距离。
　　如果f[u][1]能到达当前节点可以不必染当前点，如果到不了就买f[u][2]的那个点，因为他是最优的，顺便更新下f[u][1]。
 1 #include<bits/stdc++.h>
 2 using namespace std;  3 #define LL long long 
 4 
 5 const int maxn=100010;  6 vector<int>g[maxn];  7 int n,f[maxn][3],c[maxn];  8 void dfs(int u,int dep){  9     if(g[u].size()==0){ 10         f[u][0]=1; 11         f[u][1]=c[u];  //买 
12         f[u][2]=c[u];  //all 
13         return; 14  } 15     f[u][1]=0; 16     f[u][2]=c[u]; 17     for(auto v:g[u]){ 18         dfs(v,dep+1); 19         f[u][0]+=f[v][0]; 20         f[u][2]=max(f[u][2],f[v][2]-1); 21         f[u][1]=max(f[u][1],f[v][1]-1); 22  } 23     if(f[u][1]<=0){ 24         f[u][0]++; 25         f[u][1]=f[u][2]; 26  } 27 } 28 int main(){ 29     int fa; 30     cin>>n; 31     for(int i=2;i<=n;++i){ 32         cin>>fa; 33  g[fa].push_back(i); 34  } 35     for(int i=1;i<=n;++i)cin>>c[i]; 36     dfs(1,0); 37     cout<<f[1][0]; 38     return 0; 39 }

 

 
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄