[동적 기획] 자유 로 운 열쇠

       (key.pas/c/cpp) 
   
         n    ， n    n-1      。         
       ，      ，         ，          。    
                ，          。  ，        1
   （1               ，   ，       ，     1  
 ，           ） ，         P，          ？ 
 
     
             ，    N，    P。 
     n   ， 1~n          。  i+1         cost  keys，
     i                      。 
      n-1 ，         x,y，  x     y      。 
 
     
        ，          。 
 
   
  :key.in 
5 5 
1 2 
1 1 
1 1 
2 3 
3 4 
1 2 
1 3 
2 4 
2 5 
 
  : key.out 
7 
 
     
     20%     ， n<=20 
     30%     ， n<=30 
          ， p,n<=100, cost <= Maxint, keys<= Maxint 

비교적 기본 적 인 트 리 DP먼저 두 갈래 를 더 돌리 고 DP 를 하면 됩 니 다.상태: f [i] [j] 로 i 라 는 서브 트 리 를 표시 하고 j 의 에 너 지 를 사용 하여 얻 을 수 있 는 최대 열쇠 수 를 표시 합 니 다.전이 방정식: f [i] [j] = max (f [son [i]]] [k] + f [bro [i]] [j - k - c [i]] + v [i], f [bro [i]] [j]).가장 자 리 를 읽 을 때 먼저 무방 향도 로 읽 고 무방 향도 에 따라 나 무 를 만든다. 그렇지 않 으 면 결과 가 심각 하 다.그리고 어떤 노드 가 소모 하 는 에 너 지 는 0 이 될 수 있 기 때문에 j = 0 은 경계 조건 으로 할 수 없다.ACCode：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <bitset>

using std::max;

const char fi[] = "key.in";
const char fo[] = "key.out";
const int maxN = 110;
const int maxM = 110;
const int MAX = 0x3fffff00;
const int MIN = -MAX;

struct Edge {int dest; Edge *next; };
Edge *edge[maxN];
int f[maxN][maxM];
int bro[maxN];
int son[maxN];
int c[maxN];
int v[maxN];
int n, m;

  void init_file()
  {
    freopen(fi, "r", stdin);
    freopen(fo, "w", stdout);
  }
  
  void insert(int u, int v)
  {
    Edge *p = new Edge;
    p -> dest = v;
    p -> next = edge[u];
    edge[u] = p;
  }
  
  void readdata()
  {
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n + 1; ++i)
      scanf("%d%d", c + i, v + i);
    for (int i = 1; i < n; ++i)
    {
      int u, v;
      scanf("%d%d", &u, &v);
      insert(u, v);
      insert(v, u);
    }
  }
  
  int DP(int i, int j)
  {
    if (i == 0) return 0;
    if (f[i][j]) return f[i][j];
    if (bro[i])
      f[i][j] = max(f[i][j], DP(bro[i], j));
    if (j >= c[i])
    for (int k = 0; k + c[i] < j + 1; ++k)
    {
      f[i][j] = max(f[i][j], DP(son[i], k)
        + DP(bro[i], j - k - c[i]) + v[i]);
    }
    return f[i][j];
  }
  
  void Build(int u, int Last)
  {
    for (Edge *p = edge[u]; p; p = p -> next)
    {
      int v = p -> dest;
      if (v != Last)
      {
        Build(v, u);
        bro[v] = son[u];
        son[u] = v;
      }
    }
  }

  void work()
  {
    Build(1, 0);
    DP(1, m);
    printf("%d", f[1][m]);
  }
  
int main()
{
  init_file();
  readdata();
  work();
  exit(0);
}