Problem
Description
(W) 国的交通呈一棵树的形状。(W) 国一共有(n — 1)个城市和(n)个乡村，其中城市从(1)到(n — 1) 编号，乡村从(1)到(n)编号，且(1)号城市是首都。道路都是单向的，本题中我们只考虑从乡村通往首都的道路网络。对于每一个城市，恰有一条公路和一条铁路通向这座城市。对于城市 (i) ，通向该城市的道路（公路或铁路）的起点，要么是一个乡村，要么是一个编号比(i)大的城市。 没有道路通向任何乡村。除了首都以外，从任何城市或乡村出发只有一条道路；首都没有往 外的道路。从任何乡村出发，沿着唯一往外的道路走，总可以到达首都。
(W) 国的国王小 (W) 获得了一笔资金，他决定用这笔资金来改善交通。由于资金有限，小 (W) 只能翻修(n — 1)条道路。小 (W) 决定对每个城市翻修恰好一条通向它的道路，即从公路和铁 路中选择一条并进行翻修。小 (W) 希望从乡村通向城市可以尽可能地便利，于是根据人口调 查的数据，小 (W) 对每个乡村制定了三个参数，编号为(i)的乡村的三个参数是(a_i)，(b_i)和(c_i)。假设 从编号为(i)的乡村走到首都一共需要经过(x)条未翻修的公路与(y)条未翻修的铁路，那么该乡村 的不便利值为
在给定的翻修方案下，每个乡村的不便利值相加的和为该翻修方案的不便利值。 翻修(n — 1)条道路有很多方案，其中不便利值最小的方案称为最优翻修方案，小 (W) 自然 希望找到最优翻修方案，请你帮助他求出这个最优翻修方案的不便利值。
Input Format
第一行为正整数(n)。
接下来(n — 1)行，每行描述一个城市。其中第(i)行包含两个数(s_i,t_i)。(s_i)表示通向第(i)座城市 的公路的起点，(t_i)表示通向第i座城市的铁路的起点。如果(s_i > 0)，那么存在一条从第(s_i)座城 市通往第(i)座城市的公路，否则存在一条从第(-s_i)个乡村通往第i座城市的公路；(t_i)类似地，如 果(t_i > 0)，那么存在一条从第(t_i)座城市通往第i座城市的铁路，否则存在一条从第(-t_i)个乡村通 往第(i)座城市的铁路。
接下来(n)行，每行描述一个乡村。其中第i行包含三个数(a_i,b_i,c_i)，其意义如题面所示。
Output Format
输出一行一个整数，表示最优翻修方案的不便利值。
Sample
Input 1
6
2 3
4 5
-1 -2
-3 -4
-5 -6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Output 1
54
Input 2
9
2 -2
3 -3
4 -4
5 -5
6 -6
7 -7
8 -8
-1 -9
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
Output 2
548
Input 3
12
2 4
5 3
-7 10
11 9
-1 6
8 7
-6 -10
-9 -4
-12 -5
-2 -3
-8 -11
53 26 491
24 58 190
17 37 356
15 51 997
30 19 398
3 45 27
52 55 838
16 18 931
58 24 212
43 25 198
54 15 172
34 5 524
Output 3
5744902
Explanation
Explanation for Input 1
一种不便利值等于54的方法是：翻修通往城市2和城市5的铁路，以及通往其他城市的 公路。用→和⇒表示公路和铁路，用∗→和∗⇒表示翻修的公路和铁路，那么：
编号为1的乡村到达首都的路线为：-1 ∗→ 3 ⇒ 1，经过0条未翻修公路和1条未翻修铁 路，代价为3 × (1 + 0) × (2 + 1) = 9；
编号为2的乡村到达首都的路线为：-2 ⇒ 3 ⇒ 1，经过0条未翻修公路和2条未翻修铁 路，代价为2 × (1 + 0) × (3 + 2) = 10；
编号为3的乡村到达首都的路线为：-3 ∗→ 4 → 2 ∗→ 1，经过1条未翻修公路和0条未 翻修铁路，代价为3 × (2 + 1) × (1 + 0) = 9；
编号为4的乡村到达首都的路线为：-4 ⇒ 4 → 2 ∗→ 1，经过1条未翻修公路和1条未翻 修铁路，代价为1 × (2 + 1) × (3 + 1) = 12；
编号为5的乡村到达首都的路线为：-5 → 5 ∗⇒ 2 ∗→ 1，经过1条未翻修公路和0条未 翻修铁路，代价为2 × (3 + 1) × (1 + 0) = 8；
编号为6的乡村到达首都的路线为：-6 ∗⇒ 5 ∗⇒ 2 ∗→ 1，经过0条未翻修公路和0条未翻修铁路，代价为1 × (3 + 0) × (2 + 0) = 6；
总的不便利值为9 + 10 + 9 + 12 + 8 + 6 = 54。可以证明这是本数据的最优解。
Explanation for Input 2
在这个样例中，显然应该翻修所有公路。
Range
一共20组数据，编号为1 ∼ 20。 对于编号(le 4)的数据，(n le 20)；
对于编号为5 ∼ 8的数据，(a_i,b_i,c_i le 5)，(n le 50)；
对于编号为9 ∼ 12的数据，(n le 2000)；
对于所有的数据，(n le 20000)，(1 le a_i,b_i le 60)，(1 le c_i le 109)，(s_i,t_i)是([-n,-1] cup (i,n — 1])内的整数，任意乡村可以通过不超过40条道路到达首都。
Algorithm
(DP)
Mentality
(HNOI2018) 的 (Day2T3......) 一道据说许多人考场上看成神题的题目 (QwQ) 。
平心而论这道题确实也就那么难，顶天了 (TG T2) ，就是谁叫它放在 (Day2T3) 呢，造成了一系列误会 = = 。
那么我们看到题之后，发现了数据范围里最后一句表达的意思就是树的深度不超过 (40) ，于是难度进一步缩减 (......)
考虑倒推 (DP) ，我们设 (f[i][A][B]) 代表到了 (i) 节点，从 (i) 到根节点中有 (A) 条未翻修公路以及 (B) 条未翻修铁路，(i) 的子树中所有乡村到根节点的最小代价。那么 (DP) 式子其实就很简单了：
向左儿子走会增加一条公路，这是 (A+1) 的由来，向右儿子走增加一条铁路，这是 (B+1) 的由来，而不增加的是选择翻修到那个儿子节点的路。
如果到达叶子节点，直接枚举计算式子结果。
接下来就只有一个问题了，那就是空间不够，但是由于我们每棵树只有两颗子树，所以我们先用 (tmp) 记录下其中一个子树的 (DP) 值，再处理另一颗子树，而我们的第一维 (i) ，则变成 (deep[i]) ，也即深度。
那么答案就是 (f[1][0][0]) ，确实蛮好弄的 (......)
Code
#include<iostream>
#include<cstdio>
using namespace std;
int n,ls[20001],rs[20001];
long long f[42][42][42],tmp[42][42][42],a[20001],b[20001],c[20001];
void Save(int x,int A,int B)
{
for(int i=0;i<=A+1;i++)
for(int j=0;j<=B;j++)
tmp[x][i][j]=f[x][i][j];
}
void DP(int x,int deep,int A,int B)
{
if(x<0)
{
for(int i=0;i<=A;i++)
for(int j=0;j<=B;j++)
f[deep][i][j]=c[-x]*(a[-x]+i)*(b[-x]+j);//若为叶子节点处理 dp 值
return;
}
DP(ls[x],deep+1,A+1,B);
Save(deep+1,A+1,B);//先存下左子树的 dp 值
DP(rs[x],deep+1,A,B+1);
for(int i=0;i<=A;i++)
for(int j=0;j<=B;j++)
f[deep][i][j]=min(tmp[deep+1][i+1][j]+f[deep+1][i][j],f[deep+1][i][j+1]+tmp[deep+1][i][j]);//状态转移
}
int main()
{
cin>>n;
for(int i=1;i<n;i++)
scanf("%d%d",&ls[i],&rs[i]);
for(int i=1;i<=n;i++)
scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
DP(1,1,0,0);
cout<<f[1][0][0];
}