LOJ: 1252 - Maintaining Communities (Tree DP)

LOJ: 1252 - Maintaining Communities 
///==================================================///
///                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     101
#define inf    2000000000
#define MD     1000000000LL
#define eps    1e-9
///===============================///

vector<int>G[MX+2];
vector<int>C[MX+2];
int tsz[MX];///total size of each node
int w,dp[MX][MX];

int go(int p,int ps,int gp,int c) {
    if( !tsz[p] || ps>=tsz[p] ) {
        if( c>=0 ) return 0;
        else return inf;
    }
    int v=G[p][ps];
    int wt=C[p][ps];
    if( v==gp ) return go(p,ps+1,gp,c);
    int &ret=dp[v][c];
    if(ret!=-1) return ret;
    ret=inf;
    ///cut edge;
    ret=min(ret,1+go(p,ps+1,gp,c)+go(v,0,p,w));
    ///dont cut edge
    if(wt<=c) {
        int rem=(c-wt);
        for(int i=0; i<=rem; i++) {
            ret=min(ret,go(p,ps+1,gp,i)+go(v,0,p,rem-i));
        }
    }
    return ret;
}
int main() {
    int tc,cs=1,i,j,n,k,x,y,z;
    S(tc);
    while(tc--) {
        S2(n,w);
        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);
        }
        SET(dp);
        fr(i,1,n) {
            tsz[i]=SZ(G[i]);
            fr(j,0,w)dp[i][j]=-1;
        }
        int ans=go(1,0,-1,w);
        ///par, childNo, grand pa, wt to assign for each partition;
        printf("Case %d: %d\n",cs++,ans+1);
    }
    return 0;
}