JZOJ 5906. 【NOIP2018模拟10.15】传送门 树形DP

本文思路由Felix-Lee提供，加上了自己的理解，侵权联系删除

传送门

时间限制: 2 Sec 内存限制: 512 MB

题目描述

8102年，Normalgod在GLaDOS的帮助下，研制出了传送枪。但GLaDOS想把传送枪据为己有，于是把Normalgod
扔进了一间实验室。这间实验室是一棵有n个节点的树。现在Normalgod在一号节点，出口也在一号节点，但为了
打开它，必须经过每一个节点按下每个节点的开关，出口才能打开。GLaDOS为了杀死Normalgod，开始在实验室
里释放毒气，因此Normalgod必须尽快逃出这间实验室。
当然，Normalgod手中的传送枪是可以使用的。传送枪可以发射出两个颜色不同的传送门。Normalgod可以从其中
一个传送到另一个。尽管传送枪可以在视野范围内的任何一个经过特殊处理的表面打开一扇传送门，但这间实验室
的设计使得Normalgod只能在他所处的房间内打开一个传送门。 在已经存在了一个同颜色的传送门时，打开新的传
送门会使与它同颜色的旧门消失。传送和打开传送门所需时间为0。
显然，利用传送枪会让Normalgod更快解决谜题，可Normalgod死在了按下最后一个按钮的路上。尽管如此，
GLaDOS还是很想知道到底Normalgod最快能用多久逃出去，这对她的实验室设计方法论有重要的指导作用。作为
GLaDOS的算法模块，你要完成这个任务。本题时限为2000ms

输入

第一行一个整数n。之后n-1行，每行三个整数ui，vi，ai ,表示有一条从ui 连向vi ，花费时间为ai 的通道。

输出

一行一个数T，表示最小的脱逃时间。

样例输入

5
1 2 2
2 3 3
2 4 5
1 5 1

样例输出

13

提示

1. 设数组f[x]记录从节点x遍历x的子树最后回到x的最小时间
2. 设数组sum[x]记录子树x的所有边加起来的和
3. 设数组len[x]记录从x到的最长链
4. 对于每一棵子树x我们都可以选择接下连接y的距离用传送门直接跳过，或者我们把这个机会留给x的子树
5. 所以我们可以得到下面的动态转移方程f[x]+=min(f[y]+e[i].w*2,sum[y]*2+len[y]+e[i].w)
6. 前面那个式子代表走接下来的路，把机会留给后面，后面那个式子代表用传送门跳过当前这条路，运用贪心的思想，传送门传送的路越多，我们走的越少，所以我们直接用传送门跳到最长链，后面所有的道路都要走两条减去最长链再加上当前这条路，回来的时候走的

然后就没什么了，注意开long long

#include<cstdio>
#include<algorithm>
#define si 1000005
#define ll long long
#define re register ll
using namespace std;
struct edge {
	ll nex,to,w;
}e[si<<1];
ll n,cnt,head[si],sum[si],len[si],f[si];
inline void add(ll x,ll y,ll z) {
	e[++cnt].to=y,e[cnt].w=z,e[cnt].nex=head[x],head[x]=cnt;
}
inline void dfs(ll x,ll fa) {
	for(re i=head[x];i;i=e[i].nex) {
		ll y=e[i].to;
		if(y==fa) continue; dfs(y,x);
		len[x]=max(len[x],len[y]+e[i].w);
		sum[x]+=sum[y]+e[i].w;
		f[x]+=min(f[y]+e[i].w*2,sum[y]*2-len[y]+e[i].w);
	}
}
int main() {
	scanf("%lld",&n);
	for(re i=1;i<n;i++) {
		ll x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		add(x,y,z),add(y,x,z);
	}
	dfs(1,0);
	printf("%lld",f[1]);
	return 0;
}