HDU-4276 :The Ghost Blows Light (Tree DP)

HDU-4276 :The Ghost Blows Light
IDEA: 

    This is one of my favorite problem. Problem is giving us a weighted tree and each node 

have value associated with it.Given a time -T, we have to move from 1 to n within time also

maximizing the total value collected from nodes.

Idea is simply a tree dp. First find a shortest path (let Sdis) from 1 to n in that tree

and make weight of that path 0. Then simply do a tree dp starting from rooted tree at 1.

Each time trying to maximizing the all possible value gaining by using time of (T-Sds).

///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;
///==========CONSTANTS=============///
///  Digit     0123456789012345678 ///
#define MX     105
#define inf    200000000
#define MD     1000000000LL
#define eps    1e-9
///===============================///

vector<int>G[MX+2];
vector<int>C[MX+2];
int n,t,val[MX+2],dp[MX][505],tmp[MX+2];

int Dfs(int u,int d,int p) {
    if( u==n ) {
        t-=d;
        return 1;
    }
    for(int i=0; i<SZ(G[u]); i++) {
        int v=G[u][i],w=C[u][i];
        if( v==p )continue;
        if( Dfs( v,d+w,u )==1 ) {
            C[u][i]=0;
            return 1;
        }
    }
    return 0;
}

void go(int u,int p) {
    for(int i=0; i<=t; i++)dp[u][i]=val[u];
    for(int i=0; i<SZ(G[u]); i++) {
        int v=G[u][i],w=C[u][i];
        if( v==p ) continue;
        go(v,u);
        for(int j=0; j<=t; j++)tmp[j]=dp[u][j];/// Prev subtree
        for(int j=0; j<=t; j++) { ///Fix Time;
            if( j<(2*w) ) continue; ///Coz can't connect;
            for(int k=0; k<=j; k++) { ///For rest subtree;
                if( (j-(2*w)-k) <0 )continue;
                dp[u][j]=max( dp[u][j],tmp[k]+dp[v][ j-(2*w)-k ] );
            }
        }
    }
}

int main() {
    int i,j,x,y,z;
    while(S2(n,t)==2) {
        fr(i,1,n)G[i].clear(),C[i].clear();
        fr(i,1,n-1) {
            S2(x,y);
            S(z);
            G[x].pb(y);
            G[y].pb(x);
            C[x].pb(z);
            C[y].pb(z);
        }
        fr(i,1,n)S(val[i]);
        CLR(dp);
        Dfs(1,0,-1);
        if( t<0 ) {
            printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");
            continue;
        }
        go(1,-1);
        printf("%d\n",dp[1][t]);
    }
    return 0;
}