[나무에 다중 가방 의존 DP] BZOJ 4910 [Sdoi 2017] 사과나무.

제목 t-3-h≤k의 제한은 사실 잎 노드까지의 체인을 선택한 다음에 k개의 최대치를 선택하는 것이다(vi가 0보다 크기 때문이다).
ai>1의 점은 첫 번째를 먼저 골라서 두 번째를 선택한 것이 틀림없기 때문에 ai>1의 점을 두 개의 점 i′, i′′, i′=1, ai′=ai--1, i′를 i′의 아들로 만들 수 있다.
이 나무에 의존하는 가방은 두 개의 트리의 순서가 반대되는 후순 트리와 대기열 최적화 O (NK) 를 통해 각 점에서 K개를 선택하는 최대 가치를 구할 수 있다.
그리고 각 잎(뜯기 전의 잎)을 일일이 열거하고 두 개의 뒷순서로 옮겨다니는 DP값으로 답을 업데이트하면 된다.

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N=40010,K=500010;


bool bg;
int t,n,k,cnt,ncnt,DEPT,iG[N],a[N],v[N],lef[N],dpt[N],sz[N],son[N];
int f[51000010],g[51000010];
int val[N];
ll tot;
struct edge{
  int t,nx;
}E[N];

int Ap[N],Bp[N],pa[N],pb[N],A[N],B[N],At,Bt;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}

inline void rea(int &x){
  char c=nc(); x=0;
  for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc());
}

inline void adde(int x,int y){
  E[++cnt].t=y; E[cnt].nx=iG[x]; iG[x]=cnt;
}

void dfsf(int x){
  Ap[x]=At; sz[x]=1;
  for(int i=iG[x];i;i=E[i].nx){
    val[E[i].t]=val[x]+v[E[i].t];
    dpt[E[i].t]=dpt[x]+1;
    dfsf(E[i].t),sz[x]+=sz[E[i].t];
  }
  A[++At]=x; pa[x]=At;
}

void dfsb(int x){
  vector<int> son; Bp[x]=Bt;
  for(int i=iG[x];i;i=E[i].nx)    son.push_back(E[i].t);
  for(int i=son.size()-1;~i;i--) dfsb(son[i]);
  B[++Bt]=x; pb[x]=Bt;
}

#define F(x,y) f[(x)*(k+1)+(y)]
#define G(x,y) g[(x)*(k+1)+(y)]

//ll &F(int x,int y){ return f[(x)*(k+1)+(y)]; }
//ll &G(int x,int y){ return g[(x)*(k+1)+(y)]; }

int Q[K],Q1[K],qh,qt;

bool ed;

inline void DP(int *A,int *p,int *f){
  for(int i=1;i<=ncnt;i++){
    int x=A[i];
    int *ff=f+(i-1)*(k+1),*fc=f+i*(k+1);
    memcpy(fc,f+p[x]*(k+1),sizeof(int)*(k+1));
    //for(int j=0;j<=k;j++) fc[j]=F(p[x],j);
    if(a[x]==0) continue;
    if(a[x]==1){
      for(int j=1;j<=k;j++)
        fc[j]=max(fc[j],ff[j-1]+v[x]);
      continue;
    }
    qh=qt=1;
    Q[qh]=0; Q1[qh]=0;
    for(int j=1;j<=k;j++){
      fc[j]=max(fc[j],j*v[x]+Q1[qh]);
      while(qh<=qt && Q[qh]<=j-a[x]) qh++;
      int cur=ff[j]-j*v[x];
      while(qh<=qt && Q1[qt]int ans;

int main(){
  rea(t);
  while(t--){
    rea(n); rea(k);
    for(int i=1;i<=n;i++) iG[i]=lef[i]=val[i]=son[i]=0;
    //memset(f,0,sizeof(f));
    //memset(g,0,sizeof(g));
    cnt=0; ncnt=n; At=Bt=0; ans=0; tot=0;
    for(int i=1;i<=n;i++){
      int p; rea(p); rea(a[i]); rea(v[i]); tot+=a[i];
      if(p) adde(p,i),lef[p]=1;
      if(a[i]>1)
        a[son[i]=++ncnt]=a[i]-1,v[ncnt]=v[i],a[i]=1,adde(i,ncnt),lef[ncnt]=1;
    }
    val[1]=v[1]; dpt[1]=1;
    dfsf(1); dfsb(1);
    DP(A,Ap,f);
    DP(B,Bp,g);
    //printf("%d
",clock()-ttt);
    /*for(int i=1;i<=n;i++)
        for(int j=0;j<=k;j++)
            cout<
    for(int i=1;i<=n;i++)
      if(!lef[i]){
        int cur=min((ll)k,tot-dpt[i]);
        int *ff=f+(pa[i]-1)*(k+1),*gg=g+(pb[i]-sz[i])*(k+1);
        for(int j=0;j<=cur;j++)
          ans=max(ans,ff[j]+gg[cur-j]+val[i]);
      }
    //printf("%d
",clock()-ttt);
    printf("%d
",ans);
  }
  //printf("%d
",(&ed-&bg)/1024/1024);
    return 0;
}