洛谷P4438 [HNOI/AHOI2018]道路 题解
题意：
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\) 条未翻修的铁路，那么该乡村的不便利值为：
\[ c_i \cdot (a_i + x) \cdot (b_i + y) \] 在给定的翻修方案下，每个乡村的不便利值相加的和为该翻修方案的不便利值。 翻修 \(n-1\) 条道路有很多方案，其中不便利值最小的方案称为最优翻修方案，小 W 自然希望找到最优翻修方案，请你帮助他求出这个最优翻修方案的不便利值。
输入格式：
第一行为正整数 \(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\)，其意义如题面所示。
输出格式：
输出一行一个整数，表示最优翻修方案的不便利值。
数据范围 ： 对于所有的数据，\(n \le 20000\)，\(1 \le a_i,b_i \le 60\)，\(1 \le c_i \le 10^9\)，\(s_i,t_i\)是\([-n,-1] \cup (i,n - 1]\)内的整数，任意乡村可以通过不超过 \(40\) 条道路到达首都。
题面讲了半天，其实是给定了一棵满二叉树（国外定义），然后农村就是叶子节点。
考虑树形dp。因为树高不超过 \(40\) 的（题目说的），所以可以直接枚举没标记的边数。
设 \(f_{u,i,j}\) 表示从根到 \(u\) 有 \(i\) 条没标记的 \(L\) 边和 \(j\) 条没标记的 \(R\) 边
对于每个叶子节点枚举有多少没有被标记的 \(L\) 边和 \(R\) 边 \[ f_{u,i,j} = c_u (a_u+i)(b_u+j) \] 对于每个非叶子节点枚举标记哪条边 \[ f_{u,i,j} = \min\{f_{l,i+1,j} + f_{r,i,j},~f_{l,i,j} + f_{r,i,j+1}\} \] 最后的答案为 \(f_{1,0,0}\) 。但是还不能通过这道题，因为这道题卡空间。
注意到每次dp统计答案是自底向上的，所以当前节点的两个子节点在统计完之后就用不上了。
考虑钦定一种dp顺序，比如每次优先转移左儿子，然后用个栈维护一下当前链的有用节点。
这样第一维就只要开 \(2 \times 40 + 1\) 了。时间复杂度 \(\mathcal{O}(nk^2), k = 40\)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(4e4+15))
#define M ((int)(43))
int n,m,top,tot,a[N],b[N],c[N],s[N],t[N],num[N],stk[N],f[M * 2][M][M];
void dfs(int u,int x,int y)
{
int p = num[u] = (top ? stk[top--] : ++tot);
if(!s[u])
{
for(int i=0; i<=x; i++) for(int j=0; j<=y; j++)
f[p][i][j] = c[u] * (a[u] + i) * (b[u] + j);
return;
}
dfs(s[u], x + 1, y); dfs(t[u], x, y + 1);
int ls = num[s[u]], rs = num[t[u]];
for(int i=0; i<=x; i++) for(int j=0; j<=y; j++)
down(f[p][i][j] = f[ls][i + 1][j] + f[rs][i][j], f[ls][i][j] + f[rs][i][j + 1]);
stk[++top] = ls; stk[++top] = rs;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n; m = 2 * n - 1;
for(int i=1,u,v; i<n; i++)
{
cin >> u >> v;
s[i] = u < 0 ? (n - 1 - u) : u;
t[i] = v < 0 ? (n - 1 - v) : v;
}
for(int i=n; i<=m; i++)
cin >> a[i] >> b[i] >> c[i];
dfs(1,0,0); cout << f[num[1]][0][0] << '\n';
return 0;
}参考文献：
