BZOJ4910 : [Sdoi2017] 苹果树

问题等价于树形依赖背包，允许一条链每个点各免费一次。

设$f[i][j]$表示按DFS序考虑到$i$，体积为$j$的最大收益。

先放入不能免费的物品，等遍历完儿子后再放入必选的物品，那么$i$到根路径上所有点都只算了不能免费的部分。

然后将DFS序翻转，设$h[i][j]$表示按DFS序考虑到$i$，体积为$j$的最大收益。

等遍历完儿子后再放入必选的物品和不能免费的物品，那么$i$到根路径上所有点都没有算。

如此一来，对于每个叶子$i$，用$f[i][j]+h[i][k-j]$更新答案即可。

对于不能免费的物品，需要用单调队列优化转移。

时间复杂度$O(nk)$。

#include<cstdio>

#include<cstring>

const int N=20010,M=25520010;

int Case,n,m,K,T,i,fa[N],a[N],b[N],g[N],nxt[N],ans,F[M],H[M];

inline void add(int x,int y){nxt[y]=g[x];g[x]=y;}

inline void up(int&a,int b){a<b?(a=b):0;}

inline void solve(int*f,int A,int B){

  int i,j=0,h=1,t=0;

  static int q[500010],p[500010];

  for(i=0;i<=m;i++,j+=B){

    f[i]-=j;

    while(h<=t&&f[q[t]]<f[i])t--;

    q[++t]=i;

    while(i-q[h]>A)h++;

    p[i]=f[q[h]]+j;

  }

  memcpy(f,p,T);

}

void dfsl(int x){

  int i,j,A=a[x],B=b[x];

  if(A)solve(F+x*K,A,B);

  for(i=g[x];i;i=nxt[i]){

    memcpy(F+i*K,F+x*K,T);

    dfsl(i);

    B=b[i];

    int*s=F+x*K+1,*e=F+i*K;

    for(j=1;j<=m;j++,s++,e++)up(*s,*e+B);

  }

}

void dfsr(int x,int y){

  int i,j,A=a[x],B=b[x];

  y+=B;

  for(i=g[x];i;i=nxt[i]){

    memcpy(H+i*K,H+x*K,T);

    dfsr(i,y);

    B=b[i];

    int*s=H+x*K+1,*e=H+i*K;

    for(j=1;j<=m;j++,s++,e++)up(*s,*e+B);

  }

  if(!g[x]){

    int*s=H+x*K+m,*e=F+x*K;

    for(j=0;j<=m;j++,s--,e++)up(ans,*s+*e+y);

  }

  if(A)solve(H+x*K,A,b[x]);

}

int main(){

  scanf("%d",&Case);

  while(Case--){

    scanf("%d%d",&n,&m);

    K=m+1;T=K*sizeof(int);

    for(i=1;i<=n;i++)g[i]=0;

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

      scanf("%d%d%d",&fa[i],&a[i],&b[i]);a[i]--;

      if(fa[i])add(fa[i],i);

    }

    memset(F+K,0,T);

    memset(H+K,0,T);

    dfsl(1);

    for(i=1;i<=n;i++)g[i]=0;

    for(i=n;i;i--)if(fa[i])add(fa[i],i);

    ans=0;

    dfsr(1,0);

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

  }

  return 0;

}