题意

给定 \(n\) 个节点的树，点有点权 \(w\) ，划分成多条儿子到祖先的链，要求每条链点数不超过 \(L\) ,和不超过 \(S\)，求最少划分成几条链。

\(n\leq 10^5\) .

分析

• 贪心，从叶子节点开始向上合并，倍增计算出以一个节点为链底，能够最多到达哪个祖先 \({up}_u\)。

• 每个节点合并和时候取每个子树的 \(up\) 最浅的那个，正确性显然。

• 总时间复杂度为 \(O(nlogn)\)。

代码

#include<bits/stdc++.h>

using namespace std;

#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].last,v=e[i].to)

#define rep(i,a,b) for(int i=a;i<=b;++i)

#define pb push_back

typedef long long LL;

inline int gi(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch))	{if(ch=='-') f=-1;ch=getchar();}

	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}

	return x*f;

}

template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}

template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;}

const int N=1e5 + 7;

int n,L,edc,ans;

int head[N],fa[N][18],dep[N];

LL dis[N],S,w[N],up[N];

struct edge{

	int last,to;

	edge(){}edge(int last,int to):last(last),to(to){}

}e[N*2];

void Add(int a,int b){

	e[++edc]=edge(head[a],b),head[a]=edc;

	e[++edc]=edge(head[b],a),head[b]=edc;

}

void dfs1(int u){

	dis[u]=w[u]+dis[fa[u][0]],dep[u]=dep[fa[u][0]]+1;

	rep(i,1,17) fa[u][i]=fa[fa[u][i-1]][i-1];

	go(u)if(v^fa[u][0])

		fa[v][0]=u,dfs1(v);

}

void dfs2(int u){

	go(u)if(v^fa[u][0]){

		dfs2(v);

		if(up[u]==-1||dep[up[u]]>dep[up[v]]) up[u]=up[v];

	}

	if(up[u]==-1||dep[up[u]]>=dep[u]){

		++ans;int tl=L,x=u;LL ts=S;

		for(int i=17;~i;--i) if((1<<i)<=tl&&dis[x]-dis[fa[x][i]]<=ts){

			ts-=dis[x]-dis[fa[x][i]];

			tl-=(1<<i);

			x=fa[x][i];

		}

		up[u]=x;

	}

}

int main(){

	scanf("%d%d%I64d",&n,&L,&S);

	memset(up,-1,sizeof up);

	rep(i,1,n) {

		w[i]=gi();

		if(w[i]>S) return puts("-1"),0;

	}

	rep(i,2,n) Add(i,gi());

	dfs1(1);dfs2(1);

	printf("%d\n",ans);

	return 0;

}