[CodeForces1059E] Split the Tree

树形DP.

用倍增处理出来每个点往上能延伸出去的最远路径，nlogn

对于每个节点，如果它能被后代使用过的点覆盖，就直接覆盖，这个点就不使用，否则就ans++，让传的Max改成dp[x]

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N=;

int n,a[N],fa[N][],f[N],head[N],to[N<<],nxt[N<<],ecnt,ans,L;

inline void add(int bg,int ed) {

    nxt[++ecnt]=head[bg];to[ecnt]=ed;head[bg]=ecnt;

}

ll S,v[N][];

void dfs(int x) {

    for(int i=head[x];i;i=nxt[i])

        if(to[i]!=fa[x][]) fa[to[i]][]=x,v[to[i]][]=a[x],dfs(to[i]);

}

int Dfs(int x) {

    int Max=;

    for(int i=head[x];i;i=nxt[i]) if(to[i]!=fa[x][]) Max=max(Max,Dfs(to[i]));

    if(!Max) {

        ans++;

        return f[x]-;

    }

    return Max-;

}

int main() {

    cin>>n>>L>>S;

    for(int i=;i<=n;i++) {scanf("%d",&a[i]);if(a[i]>S) return puts("-1"),;}

    for(int i=,x;i<n;i++)     scanf("%d",&x),add(x,i+),add(i+,x);

    dfs();

    for(int i=;(<<i)<=L;i++) {

        for(int j=;j<=n;j++) {

            fa[j][i]=fa[fa[j][i-]][i-];

            v[j][i]=v[fa[j][i-]][i-]+v[j][i-];

        }

    }

    for(int i=;i<=n;i++) {

        ll sum=a[i];int now=i;f[i]=;

        for(int j=;~j&&sum<=S;j--) {

            if(fa[now][j]&&sum+v[now][j]<=S&&f[i]+(<<j)<=L)

                            sum+=v[now][j],f[i]+=<<j,now=fa[now][j];

        }

    }

    Dfs();

    cout<<ans;

    return ;

}    

Split the Tree