题目概述

把一棵有权值的树分成若干条儿子到祖先的路径，每条路径节点个数不能超过 $L$ ，节点权值和不能超过 $S$ ，问最少分成多少路径。

解题报告

一个不知道正确性的解法，大佬可以来证明或者证伪一下QAQ。

这是法老的解法，我帮他打代码。可以发现不能交到其实并没有什么用，两条交起来的合法路径肯定有方法砍成不相交的合法路径。

所以可以直接贪心，尽量从深度大的地方开始覆盖（数据结构维护），用倍增处理一下最远能覆盖到的地方就好了。

示例程序

#include<cstdio>
#include<algorithm>
#include<set>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=100000,Log=17;

int n,m,w[maxn+5],dep[maxn+5],top[maxn+5],ST[maxn+5][Log+5];LL S,sum[maxn+5][Log+5];
int E,lnk[maxn+5],son[maxn+5],nxt[maxn+5];int fat[maxn+5],ans;set< pair<int,int> > s;

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void Dfs(int x,int pre=0){dep[x]=dep[pre]+1;ST[x][0]=pre;sum[x][0]=w[pre];
    for (int j=1;j<=Log;j++) sum[x][j]=sum[x][j-1]+sum[ST[x][j-1]][j-1],ST[x][j]=ST[ST[x][j-1]][j-1];
    for (int j=lnk[x];j;j=nxt[j]) Dfs(son[j],x);int p=x,tot=1;LL now=w[p];
    for (int j=Log;~j;j--) if (ST[p][j]&&tot+(1<<j)<=m&&now+sum[p][j]<=S) tot+=1<<j,now+=sum[p][j],p=ST[p][j];top[x]=p;
}
int getfa(int x) {return x==fat[x]?x:fat[x]=getfa(fat[x]);}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%lld",&n,&m,&S);for (int i=1;i<=n;i++) {scanf("%d",&w[i]);if (w[i]>S) return puts("-1"),0;}
    for (int i=2,fa;i<=n;i++) scanf("%d",&fa),Add(fa,i);Dfs(1);
    for (int i=1;i<=n;i++) s.insert(mp(-dep[i],i)),fat[i]=i;
    while (!s.empty()){
        int x=(*s.begin()).sc,p=getfa(x);top[x]=getfa(top[x]);
        while (p!=top[x]) s.erase(mp(-dep[p],p)),p=fat[p]=getfa(ST[p][0]);
        if (s.count(mp(-dep[top[x]],top[x]))) s.erase(mp(-dep[top[x]],top[x]));ans++;
    }printf("%d\n",ans);return 0;
}