黑白树
黑白树
https://ac.nowcoder.com/acm/problem/13249
思路:从子节点染色然到父节点,我们看每个节点的覆盖长度还有他子节点的覆盖长度,如果他的覆盖长度dep[u]>dp[v]-1他子节点的覆盖长度那么我们就去用大的更新dep[u]=max(dep[u],dep[v]-1)然后我们记录一下当覆盖距离为0时,他就只能靠自己去覆盖
#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; }