链接: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.要想解决这个问题 首先要解决基础版本,把这个问题放到 x轴上:起初所有点都是白色,每次对一个白色的点进行操作,每次操作会将包括该点及以后的k[i]个点染黑,问最少染色次数。

2 —— 5 —— 1 —— 1 —— 1

可能开始思路贪心都差不多,从左到右一直染色,直到不能再染,再开一种新的颜色。

这种思路很明显对于上面红色的例子就不对,正确结果应该是2,贪心思路得到为4

原因在于:2可以染色到第三个点,但是第三个点如果被第二个点5染色的话 结果会更优——因为5不仅可以染3还可以染4 5

所以说,当1第一个点染到不能再染的时候,应该让看一看如果然之前的某个点会不会有更长的距离。

所以我们需要记录一下之前哪个点染到当前这个点能染的距离更长,那就染那个点来代替这个点。

所以伪代码也给出:

int ans=0,res=0;/// res 统计结果 ans 标记之前的点到该点后能够往后延伸的最大距离 for(int i=1;i<=n;i++){  if(!dp[i]){///染不到这个点了 res++;
           dp[i+1]=max(num[i]-1,ans-1);///这个点就染 判断一下 从之前的点染好还是当前点染  } else dp[i+1]=dp[i]-1;///正常递推 ans=max(num[i],ans);///过程中记录 ans--;///下一个点ans就要--  }

有人会质疑之前的染过一次的点会不会染第二次答案是不可能的..(因为如果当前!dp[i],说明染过的点刚好到当前点之后为0,那么最少最少num[i]>=1)

2.现在把问题进阶一下,放到树上:

其实放到树上的思路是一模一样的,dp[i+1]变为 当前节点i的父节点就可以了。

我们判断当前dp[u]还可不可以染色,直接用dfs返回子树中到达当前还可以染色的最大距离,每次dp[u]不能染色的时候,答案就要++,将dp[u]更新成最大染色距离,再继续使其染色。

具体代码:

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
const ll INF=1e18;
const int maxn=1e5+18;
const int mod=1e9+7;
inline bool read(ll &num)
{char in;bool IsN=false;in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
vector<int>g[maxn];
int num[maxn];
int dp[maxn];///未使用过的保留的最大值
int res=0;
int dfs(int u,int fa){
    int ans=num[u];
    for(int e:g[u]){
        ans=max(ans,dfs(e,u));
    }
    if(dp[u]==0){
        res++;
        dp[u]=ans;
    }
    dp[fa]=max(dp[fa],dp[u]-1);
    return ans-1;
}
int main()
{
    read(n);
    for(int i=2;i<=n;i++){
        int x;scanf("%d",&x);
        g[x].push_back(i);
    }
    for(int i=1;i<=n;i++) scanf("%d",&num[i]);
    dfs(1,1);
    printf("%d\n",res);
    return 0;
}
/**
7 2 1
2 5
3 7
**/
	

这题代码还是比较短,比较侧重于思维和dp的推法,想了一天,不过做出来也算有所收获。

精髓在于 每个点维护的不是答案值了 而是从当前点出发还能染色的最大距离,如果当前点被之前的点染不到了,那么该点就要从该点出发重新染色,染色的话选择能染的最多的距离,就可以保证最优。