P1612 [yLOI2018] 树上的链 题解

思路

看到条件 \(2\)，我们得知：这个节点对应的最长链，一定在这个节点到根节点的简单路径上。
所以我们记录 \(1\) 到 \(i\) 之间的权值和，记为 \(sum_i\)。因为权值是正整数，所以满足单调性，可以二分。

如何二分路径上的点呢？我们维护一个与当前 dfs 同步的栈，记录从根节点到当前节点的简单路径。二分栈里的点就行了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,w[N],c[N],sum[N],st[N],ans[N],top;
int head[N],to[N<<1],nxt[N<<1],idx;
void add(int x,int y){to[++idx]=y,nxt[idx]=head[x],head[x]=idx;}
void dfs(int x,int fa)
{
	st[++top]=x,sum[x]=sum[fa]+w[x];
	int l=1,r=top;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(sum[x]-sum[st[mid-1]]<=c[x])r=mid-1;
		else l=mid+1;
	}
	ans[x]=max(ans[x],top-l+1);
	for(int i=head[x];i;i=nxt[i])dfs(to[i],x);
	top--;
}
signed main()
{
	scanf("%lld",&n);
	for(int i=2,x;i<=n;i++)
	{
		scanf("%lld",&x);
		add(x,i);
	}
	for(int i=1;i<=n;i++)ans[i]=1;
	for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
	for(int i=1;i<=n;i++)scanf("%lld",&c[i]);
	dfs(1,0);
	for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
}