题目大意
几乎同HNOI2018道路，但将题面中的"小 W 决定对每个城市翻修恰好一条通向它的道路，即从公路和铁路中选择一条并进行翻修"这句话删去，即改为可以任意选择$n-1$条边翻修。
数据范围不变。
题解
考虑朴素DP。
即，在可以通过原题的代码的基础上，加上一维表示已选择的边的数量，同时转移上多出两边都选和都不选的方案。
复杂度$O(n2d2)$($d$为深度，$d leq 40$)，30分。
考虑优化，然而从dp的角度较难下手。
注意到有一维跟数量有关，同时打表发现，若令答案关于选择边的数量的函数，这个函数单增，且斜率(即差分后)也是单增的。
于是考虑带权二分(出题人那边叫凸优化？)。
删除最后一维，二分斜率$k$，每次转移时若新加入一条边，则强制加上$k$的贡献。
这样，可以通过控制$k$的大小来控制得到的最优解中选择的边的数量，$k$大则选的边减少，$k$小则选的边增多。
二分到最优解选择的边数恰好为$n-1$时即可停止。
复杂度$O(nd^2log k)$，其中$k$为斜率的值域。
——然而以上部分博主考试都想到了
但是，有时会出现二分不到$n-1$的情况。
具体来说，比如需要$3$条边，而最后二分的结果却一直在$2$和$4$之间来回变化。
有两种解决方案，一种是开long double，并在最后强制认为选到了$3$，即，对$4$或$2$得到的结果$f$，令$ans=f-3k$（本来应是$ans=f-4k$）。
——然后就会像博主一样被卡常$0.1$秒变成60分，需要调斜率值域才能过。
第二种，在dp统计方案时，若某个转移的价值和目前为止的最优值相同，但选取次数较最优值更少，那么更新选取次数为新的更小的选取次数。
然后在统计答案时若出现这种情况，那认定$2$是正确的，选择$ans=f_2-3*k$即可。
这样就可以开long long了!
然后程序就快了整整3倍，无压力通过......
第二种方法来自XZK dalao。
(即现场rk1 205 pts的dalao，rk2 才160，蒟蒻博主rk4 才80 pts，现场有接近80个35-45分的人......)
事实证明，对带权二分的理解还不到位......
代码:
#include<cstdio>
#include<cstring>
using namespace std;
#define print(...) fprintf(stderr,__VA_ARGS__)
typedef long long ll;
const int N=20009;
const int D=49;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0' || '9'<ch){if(ch=='-')f=-1;ch=getchar();}
while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar();
return x*f;
}
inline bool chkmin(ll &a,ll b){if(a>b)return a=b,1;return 0;}
int n,top;
int ch[N][2];
ll a[N],b[N],c[N],inc;
ll f[D*2][D][D],h[D*2][D][D],g[D][D],cg[D][D];
bool v[D*2][D][D],tv[D][D];
inline void dfs(int u,int dep)
{
if(u<0)
{
top++;
memset(v[top],0,sizeof(v[top]));
for(int i=0;i<=dep;i++)
for(int j=0;j+i<=dep;j++)
{
f[top][i][j]=c[-u]*(a[-u]+i)*(b[-u]+j);
v[top][i][j]=1;
h[top][i][j]=0;
}
return;
}
dfs(ch[u][0],dep+1);
dfs(ch[u][1],dep+1);
for(int i=0;i<=dep;i++)
for(int j=0;j+i<=dep;j++)
{
g[i][j]=1e18;tv[i][j]=0;
if(v[top-1][i][j] && v[top][i][j+1])
{
if(chkmin(g[i][j],f[top-1][i][j]+f[top][i][j+1]+inc))
tv[i][j]=1,cg[i][j]=h[top-1][i][j]+h[top][i][j+1]+1;
else if(g[i][j]==f[top-1][i][j]+f[top][i][j+1]+inc)
chkmin(cg[i][j],h[top-1][i][j]+h[top][i][j+1]+1);
}
if(v[top-1][i+1][j] && v[top][i][j])
{
if(chkmin(g[i][j],f[top-1][i+1][j]+f[top][i][j]+inc))
tv[i][j]=1,cg[i][j]=h[top-1][i+1][j]+h[top][i][j]+1;
else if(g[i][j]==f[top-1][i+1][j]+f[top][i][j]+inc)
chkmin(cg[i][j],h[top-1][i+1][j]+h[top][i][j]+1);
}
if(v[top-1][i][j] && v[top][i][j])
{
if(chkmin(g[i][j],f[top-1][i][j]+f[top][i][j]+inc+inc))
tv[i][j]=1,cg[i][j]=h[top-1][i][j]+h[top][i][j]+2;
else if(g[i][j]==f[top-1][i][j]+f[top][i][j]+inc+inc)
chkmin(cg[i][j],h[top-1][i][j]+h[top][i][j]+2);
}
if(v[top-1][i+1][j] && v[top][i][j+1])
{
if(chkmin(g[i][j],f[top-1][i+1][j]+f[top][i][j+1]))
tv[i][j]=1,cg[i][j]=h[top-1][i+1][j]+h[top][i][j+1];
else if(g[i][j]==f[top-1][i+1][j]+f[top][i][j+1])
chkmin(cg[i][j],h[top-1][i+1][j]+h[top][i][j+1]);
}
}
top--;
memset(v[top],0,sizeof(v[top]));
for(int i=0;i<=dep;i++)
for(int j=0;j+i<=dep;j++)
{
v[top][i][j]=tv[i][j];
f[top][i][j]=g[i][j];
h[top][i][j]=cg[i][j];
}
}
int main()
{
n=read();
for(int i=1;i<n;i++)
ch[i][0]=read(),ch[i][1]=read();
for(int i=1;i<=n;i++)
a[i]=read(),b[i]=read(),c[i]=read();
ll l=-1e14,r=1e14,ans=1e18;
while(l<=r)
{
inc=l+r>>1;
dfs(1,top=0);
if(h[1][0][0]<n-1)
{
ans=f[1][0][0]-(n-1)*inc;
r=inc-1;
}
else if(h[1][0][0]>n-1)
l=inc+1;
else
{
ans=f[1][0][0]-(n-1)*inc;
break;
}
}
printf("%lld
",ans);
return 0;
}