[POJ 1155]TELE(ツリーdp)

タイトルの説明
トランスファゲート
問題解
size[i]は、iをベースとしたサブツリーにいくつかのリーフノードがあることを示す.f[i][j]は、iをルートとするサブツリーのうち、j個のリーフノードを選択した最大収益を表す.では、f[x][j+k]=max(f[x][j+k],last[j]+f[v[i]][k]-c[i]);注意現在更新されている状態用の元の状態は更新されたばかりの状態ではないので、last配列で前の状態を保存して更新します.
コード#コード#

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int max_n=3e3+5;
const int max_e=max_n*2;
const int INF=2e9;

int n,m,k,x,y;
int f[max_n][max_n],size[max_n],last[max_n];
int tot,next[max_e],point[max_n],v[max_e],c[max_e];

inline void add(int x,int y,int z){++tot;next[tot]=point[x];point[x]=tot;v[tot]=y;c[tot]=z;}
inline void treedp(int x,int fa){
    for (int i=point[x];i;i=next[i])
      if (v[i]!=fa){
        treedp(v[i],x);
        for (int j=0;j<=size[x];++j) last[j]=f[x][j];
        for (int j=0;j<=size[x];++j)
          for (int k=1;k<=size[v[i]];++k)
            f[x][j+k]=max(f[x][j+k],last[j]+f[v[i]][k]-c[i]);

        size[x]+=size[v[i]];
      }
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n-m;++i){
        scanf("%d",&k);
        for (int j=1;j<=k;++j){
            scanf("%d%d",&x,&y);
            add(i,x,y),add(x,i,y);
        }
    }
    for (int i=1;i<=n;++i)
      for (int j=1;j<=n;++j)
        f[i][j]=-INF;
    memset(size,0,sizeof(size));
    for (int i=n-m+1;i<=n;++i) scanf("%d",&f[i][1]),size[i]=1;
    treedp(1,0);
    for (int i=m;i>=0;--i)
      if (f[1][i]>=0){
        printf("%d
",i);
        return 0;
      }
}

まとめ
前に木のリュックの穴がどこにあったか自分で感じました.状態の問題かもしれませんが、現在更新されている状態用の元の状態は更新されたばかりの状態ではありません.