「AHOI/HNOI2018」道路

问题描述

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 (ai + x) \cdot (bi + 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$，其意义如题面所示。

输出格式

输出一行一个整数，表示最优翻修方案的不便利值。

样例输入

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

样例输出

54

提示

共 $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 10^9$，$s_i, t_i$ 是 $[−n, −1] \cap (i, n − 1]$ 内的整数，任意乡村可以通过不超过 $40$ 条道路到达首都。

挺裸的dp，令$f[i][x][y]$表示从根节点到$i$，翻修了$x$条公路，$y$条铁路，然后直接dp算一算就行了。注意到题目中的深度限制，因此可以每个深度开一个dp数组来优化空间。还可以直接定二维状态算。

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 40010
#define ll long long
using namespace std;
int n,ls[N],rs[N],a[N],b[N],c[N];
ll f[44][44][44];
void DP(int x,int d)
{
	if(x>=n)
	{
		for(int i=0;i<=d;i++)
		for(int j=0;j<=d-i;j++)f[d][i][j]=1ll*c[x-n+1]*(a[x-n+1]+i)*(b[x-n+1]+j);
		return;
	}
	DP(ls[x],d+1);ll g[44][44];
	for(int i=0;i<=d+1;i++)
	for(int j=0;j<=d+1-i;j++)g[i][j]=f[d+1][i][j];
	DP(rs[x],d+1);
	for(int i=0;i<=d;i++)
	for(int j=0;j<=d-i;j++)f[d][i][j]=min(g[i+1][j]+f[d+1][i][j],g[i][j]+f[d+1][i][j+1]);
}
int main()
{
	int i,j,k,x,y;
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		if(x<0)x=n-1-x;
		if(y<0)y=n-1-y;
		ls[i]=x;rs[i]=y;
	}
	for(i=1;i<=n;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]);
	DP(1,0);printf("%lld",f[0][0][0]);
}