E79 树上背包 P1270 “访问”美术馆

// 树上背包 O(2000*6000)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=6005;
int head[N],idx;
struct E{int v,t,ne;}e[N];
void add(int u,int v,int t){
  e[++idx]={v,t,head[u]};
  head[u]=idx;
}
int n,tot,ans,f[N][N],sz[N];

void build(int u,int fa){
  int tim,pic;
  scanf("%d%d",&tim,&pic);
  add(fa,u,tim*2);
  if(!pic){
    build(++tot,u);
    build(++tot,u);
  }
  else while(pic--)add(u,0,5);
}
void dfs(int u){
  for(int i=head[u];i;i=e[i].ne){
    int v=e[i].v,t=e[i].t;
    dfs(v);
    sz[u]+=sz[v]+t;
    for(int j=min(n,sz[u]);j>=t;j--)
      for(int k=0;k<=min(j-t,sz[v]);k++)
        f[u][j]=max(f[u][j],f[u][j-k-t]+f[v][k]);
  }
}
int main(){
  scanf("%d",&n);n--;
  tot=1;
  build(++tot,1);
  f[0][0]=1; //每个叶子有一幅画
  dfs(1);
  printf("%d\n",f[1][n]);
}