题目描述
一棵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
思路：
从子节点染色然到父节点，我们看每个节点的覆盖长度还有他子节点的覆盖长度，如果他的覆盖长度dep[u]>dp[v]-1他子节点的覆盖长度那么我们就去用大的更新dep[u]=max(dep[u],dep[v]-1)然后我们记录一下当覆盖距离为0时，他就只能靠自己去覆盖
AC
#include <cstdio> #include <cstring> #include <algorithm> #include <set> #include<iostream> #include<vector> #include<queue> #include<stack> //#include<bits/stdc++.h> using namespace std; typedef long long ll; #define SIS std::ios::sync_with_stdio(false) #define space putchar(' ') #define enter putchar('\n') #define lson root<<1 #define rson root<<1|1 typedef pair<int,int> PII; const int mod=100000000; const int N=2e6+10; const int M=1e3+10; const int inf=0x7f7f7f7f; const int maxx=2e5+7; ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } ll lcm(ll a,ll b) { return a*(b/gcd(a,b)); } template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar('0' + x % 10); } ll qsm(int a,int b,int p) { ll res=1%p; while(b) { if(b&1) res=res*a%p; a=1ll*a*a%p; b>>=1; } return res; } struct node { int to,nex; }edge[N]; int san[N]; int unsan[N]; int head[N],tot; int ans; void add(int u,int v) { edge[++tot].to=v; edge[tot].nex=head[u]; head[u]=tot; } void dfs(int u,int fa) { for(int i=head[u];i!=0;i=edge[i].nex) { int v=edge[i].to; if(v==fa)continue; dfs(v,u); san[u]=max(san[u],san[v]-1); unsan[u]=max(unsan[u],unsan[v]-1); } if(unsan[u]==0) { unsan[u]=san[u];ans++; } } int main() { SIS; int n,k; cin>>n; // memset(head,-1,sizeof head); for(int i=2;i<=n;i++) { int u; cin>>u; add(u,i); //add(i,u); } for(int i=1;i<=n;i++) cin>>san[i]; dfs(1,-1); cout<<ans<<endl; return 0; }
![[UVA1364 | POJ | NC]Knights of the Round Table | Tarjan 求点双 | 二分图 | 综合图论](https://ucc.alicdn.com/pic/developer-ecology/d14f6beadb884a3cb2d6c8a10981c6cd.png?x-oss-process=image/resize,h_160,m_lfit)