牛客树形dp —— 黑白树
黑白树
https://ac.nowcoder.com/acm/problem/13249
链接：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的推法，想了一天，不过做出来也算有所收获。
精髓在于 每个点维护的不是答案值了 而是从当前点出发还能染色的最大距离，如果当前点被之前的点染不到了，那么该点就要从该点出发重新染色，染色的话选择能染的最多的距离，就可以保证最优。
