[HOJ] 326 - Rivers

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> s[105];
int w[105]={0},p[105],c[105]={0};
int next[105],son[105],dp[105][105][55],d[105],k;
void dfs(int v,int add){
    int i;
    d[v]=add;
    for(i=0;i<s[v].size();i++)
        dfs(s[v][i],add+c[s[v][i]]);
}
void calc(int v){
    if(son[v]!=-1) calc(son[v]);
    if(next[v]!=-1) calc(next[v]);
    int i,j,l,x,y;
    for(i=p[v];i!=-1;i=p[i]){
        for(j=0;j<=k;j++){
            for(l=0;l<=j;l++){
                //no
                if(son[v]!=-1) x=dp[son[v]][i][l]; else x=0;
                if(next[v]!=-1) y=dp[next[v]][i][j-l]; else y=0;
                if(dp[v][i][j]==-1) dp[v][i][j]=x+y+w[v]*(d[v]-d[i]);
                else dp[v][i][j]=min(x+y+w[v]*(d[v]-d[i]),dp[v][i][j]);
                //set
                if(j-l>0){
                    if(son[v]!=-1) x=dp[son[v]][v][l]; else x=0;
                    if(next[v]!=-1) y=dp[next[v]][i][j-l-1]; else y=0;
                    if(dp[v][i][j]==-1) dp[v][i][j]=x+y;
                    else dp[v][i][j]=min(x+y,dp[v][i][j]);
                }
            }
        }

    }
}
int main(){
    int n,i,j;
    scanf("%d%d",&n,&k);
    p[0]=-1;
    memset(son,-1,sizeof(son));
    memset(next,-1,sizeof(next));
    memset(dp,-1,sizeof(dp));
    for(i=1;i<=n;i++){
        scanf("%d%d%d",&w[i],&p[i],&c[i]);
        s[p[i]].push_back(i);
        next[i]=son[p[i]];
        son[p[i]]=i;
    }
    dfs(0,0);
    calc(0);
    printf("%d\n",dp[son[0]][0][k]);
}