# 星星灰暗着。

### 题解 P4438 【[HNOI/AHOI2018]道路】

posted on 2018-04-17 10:58:59 | under 题解 |

## 考场上的我是多SB才没想到这题的写法啊......我连树链剖分都没想到啊.....

#include<cstdio>
#include<cstring>
#define neko 100010
#define chkmin(a,b) ((a)<(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
int n,a[neko],b[neko],c[neko],dfn[neko],son[neko][2];
long long dp[110][50][50];
void dfs(int u,int now,int rd,int tr)
{
dfn[u]=now;
if(u>=n)//countries are leaves
{
//  memset(dp[dfn[u]],0,sizeof(dp[dfn[u]]));
f(i,0,rd)
f(j,0,tr)
dp[dfn[u]][i][j]=1ll*c[u]*1ll*(a[u]+i)*1ll*(b[u]+j);
return;
}
dfs(son[u][0],now+1,rd+1,tr),dfs(son[u][1],now+2,rd,tr+1);
f(i,0,rd)
f(j,0,tr)
dp[dfn[u]][i][j]=chkmin(dp[dfn[son[u][0]]][i][j]+dp[dfn[son[u][1]]][i][j+1],
dp[dfn[son[u][0]]][i+1][j]+dp[dfn[son[u][1]]][i][j]);
}
int main()
{
int x,y;
scanf("%d",&n);
f(i,1,n-1)
{
scanf("%d%d",&x,&y),x=(x<0)?(-x+n-1):x,y=(y<0)?(-y+n-1):y;
son[i][0]=x,son[i][1]=y;
}
f(i,0,n-1)scanf("%d%d%d",&a[i+n],&b[i+n],&c[i+n]);
dfs(1,1,0,0),printf("%lld\n",dp[dfn[1]][0][0]);
return 0;
}