实际就是一道简单的树形dp
设f[u][i][j]表示从根结点到结点u经过i条未翻修公路，j条未翻修铁路的贡献最小值
边界条件：f[leaf][i][j]=(A+i)(B+j)C （题目上公式给的是c(a+i)(b+j)，而不是a(b+i)(c+j)）
转移方程：f[x][i][j]=min(f[ls][i+1][j]+f[rs][i][j],f[ls][i][j]+f[rs][i][j+1]) （ls，rs表示公路/铁路的起点）
这题有点卡空间qwqwq
#include <bits/stdc++.h>
#define N 40003
#define ll long long
#define getchar nc
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register ll x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[25];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
inline ll Min(register ll a,register ll b)
{
return a<b?a:b;
}
int n;
int S[N],T[N],dp[N];
int a[N],b[N],c[N];
ll f[N][42][42];
inline void dfs(register int x)
{
if(x>=n)
{
for(register int i=0;i<=dp[x];++i)
for(register int j=0;j<=dp[x];++j)
f[x][i][j]=1ll*(a[x]+i)*(b[x]+j)*c[x];
return;
}
dp[S[x]]=dp[T[x]]=dp[x]+1;
dfs(S[x]),dfs(T[x]);
for(register int i=0;i<=dp[x];++i)
for(register int j=0;j<=dp[x];++j)
f[x][i][j]=Min(f[S[x]][i][j]+f[T[x]][i][j+1],f[S[x]][i+1][j]+f[T[x]][i][j]);
}
int main()
{
n=read();
for(register int i=1;i<n;++i)
{
S[i]=read(),T[i]=read();
if(S[i]<0)
S[i]=-S[i]+n-1;
if(T[i]<0)
T[i]=-T[i]+n-1;
}
for(register int i=n;i<n<<1;++i)
a[i]=read(),b[i]=read(),c[i]=read();
dfs(1);
write(f[1][0][0]);
return 0;
}