UVALive 4015 트리 dp

제목 대의:
한 뿌리 노드에서 출발하여 최대 x의 길이를 걷고, 최대 몇 개의 노드를 지나갈 수 있는지 물어보면, 그림은 한 그루의 나무임을 보증한다.
 
dp[0][i][j], i점에서 뿌리를 내린 자수에서 j점을 지나 i로 돌아오는 데 최소 몇 시간이 걸린다는 뜻이다. dp[1][i][j], 같은 이치지만 i로 돌아가지 않아도 된다는 뜻이다. 그러면 아들이 아버지에게 끊임없이 갱신하는 4가지 상황이 있다.
1.if(dp[0][u][k+j]<0 || dp[0][u][k+j]>dp[0][v][j]+dp[0][u][k]+2*e[i].d)                    dp[0][u][k+j]=dp[0][v][j]+dp[0][u][k]+2*e[i].d;
2.if(dp[1][u][k+j]<0 || dp[1][u][k+j]>dp[0][v][j]+dp[0][u][k]+e[i].d)                    dp[1][u][k+j]=dp[0][v][j]+dp[0][u][k]+e[i].d;
3.if(dp[1][u][k+j]<0 || dp[1][u][k+j]>dp[1][v][j]+dp[0][u][k]+e[i].d)                    dp[1][u][k+j]=dp[1][v][j]+dp[0][u][k]+e[i].d;
4.if(dp[1][u][k+j]<0 || dp[1][u][k+j]>dp[0][v][j]+dp[1][u][k]+2*e[i].d)                    dp[1][u][k+j]=dp[0][v][j]+dp[1][u][k]+2*e[i].d;
 

  1 #include <cstdio>

  2 #include <cstring>

  3 #include <iostream>

  4 #include <algorithm>

  5 #include <cmath>

  6 

  7 using namespace std;

  8 #define N 505

  9 #define ll long long

 10 ll dp[2][N][N];

 11 int fa[N] , n , m;

 12 int first[N],k;

 13 

 14 struct Edge{

 15     int y , next , d;

 16     Edge(int y=0 , int next=0 , int d=0):y(y),next(next),d(d){}

 17 }e[N<<1];

 18 

 19 void add_edge(int x , int y , int d)

 20 {

 21     e[k] = Edge(y , first[x] , d);

 22     first[x] = k++;

 23 }

 24 

 25 void dfs(int u)

 26 {

 27     dp[0][u][1] = 0;

 28     for(int i=first[u] ; ~i ; i=e[i].next){

 29         int v = e[i].y;

 30         dfs(v);

 31         for(int k=n ; k>=1 ; k--)

 32         {

 33             if(dp[0][u][k]<0) continue;

 34             for(int j=1 ; j<n ; j++){

 35                 if(dp[0][v][j]<0) continue;

 36                 if(dp[0][u][k+j]<0 || dp[0][u][k+j]>dp[0][v][j]+dp[0][u][k]+2*e[i].d)

 37                     dp[0][u][k+j]=dp[0][v][j]+dp[0][u][k]+2*e[i].d;

 38                 if(dp[1][u][k+j]<0 || dp[1][u][k+j]>dp[0][v][j]+dp[0][u][k]+e[i].d)

 39                     dp[1][u][k+j]=dp[0][v][j]+dp[0][u][k]+e[i].d;

 40 

 41                 if(dp[1][v][j]<0) continue;

 42                 if(dp[1][u][k+j]<0 || dp[1][u][k+j]>dp[1][v][j]+dp[0][u][k]+e[i].d)

 43                     dp[1][u][k+j]=dp[1][v][j]+dp[0][u][k]+e[i].d;

 44             }

 45             if(dp[1][u][k]<0) continue;

 46             for(int j=1 ; j<=n ; j++){

 47                 if(dp[0][v][j]<0) continue;

 48                 if(dp[1][u][k+j]<0 || dp[1][u][k+j]>dp[0][v][j]+dp[1][u][k]+2*e[i].d)

 49                     dp[1][u][k+j]=dp[0][v][j]+dp[1][u][k]+2*e[i].d;

 50             }

 51         }

 52     }

 53 }

 54 

 55 int main()

 56 {

 57     #ifndef ONLINE_JUDGE

 58         freopen("a.in" , "r" , stdin);

 59     #endif // ONLINE_JUDGE

 60     int cas = 0;

 61     while(scanf("%d" , &n) , n)

 62     {

 63         printf("Case %d:
" , ++cas);

 64         memset(first , -1 , sizeof(first));

 65         k = 0;

 66         for(int i=1 ; i<=n ; i++) fa[i]=i;

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

 68             int u,v,d;

 69             scanf("%d%d%d" , &u , &v , &d);

 70             u++ , v++;

 71             add_edge(v , u , d);

 72             fa[u] = v;

 73         }

 74         int st;

 75         for(int i=1 ; i<=n ; i++)

 76             if(fa[i]==i) st = i;

 77 

 78         memset(dp , -1 , sizeof(dp));

 79         dfs(st);

 80         /*debug

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

 82             for(int j=1 ; j<=n ; j++){

 83                 printf("%4I64d" , dp[1][i][j]);

 84             }

 85             cout<<endl;

 86         }*/

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

 88         for(int i=0 ; i<m ; i++){

 89             int x;

 90             scanf("%d" , &x);

 91             int ret = 0;

 92             for(int t=1 ; t<=n ; t++){

 93               //  cout<<dp[0][1][t]<<" "<<dp[1][1][t]<<endl;

 94                 if((dp[0][st][t]<=x && dp[0][st][t]>=0) || (dp[1][st][t]<=x && dp[1][st][t]>=0))

 95                     ret = max(ret , t);

 96             }

 97             printf("%d
" , ret);

 98         }

 99     }

100     return 0;

101 }