solution
比较容易想到的一个思路就是从深度更大的点开始选,每当遇到没有没变黑的点就选择它。
但是这样实际上是有问题的,选择当前没有被染色的点向上可以伸长的长度可能还不如选择其子树中的某个点更优。我们可以通过调整选择顺序,使得先选择这个更优的点。
所以我们每次更新K[u]为K[u]和所有K[v]-1中更大的那个。然后向上延伸即可。
code
/* * @Author: wxyww * @Date: 2020-04-08 08:32:00 * @Last Modified time: 2020-04-08 09:36:43 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 100010; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } struct node { int v,nxt; }e[N << 1]; int head[N],ejs; void add(int u,int v) { e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs; } int K[N],ans,fa[N],n,dep[N]; int dfs(int u) { dep[u] = dep[fa[u]] + 1; int mn = n + 1; for(int i = head[u];i;i = e[i].nxt) { mn = min(mn,dfs(e[i].v)); K[u] = max(K[u],K[e[i].v] - 1); } if(mn > dep[u]) { ans++; // printf("%d\n",u); return dep[u] - K[u] + 1; } return mn; } int main() { // freopen("1.in","r",stdin); n = read(); for(int i = 2;i <= n;++i) { fa[i] = read(); add(fa[i],i); } for(int i = 1;i <= n;++i) K[i] = read(); dfs(1); cout<<ans<<endl; return 0; }