【NOIP2018模拟赛2018.10.17】传送门 （portal）

题目

题解

— 是树形dp呢
f[x][0]：x和x的子树里没有传送门
f[x][1]：x和x的子树里有传送门
如果不用传送门的话，每条边跑两次（下去，回来）
用了的话，就只需要跑下去就行了，但是如果儿子用了传送门，还是要跑回来的
（因为只能同时存在两个传送门）

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=1e6+5;
const long long null=1e15;

int n;
int head[MAXN],to[MAXN*2],next[MAXN*2],w[MAXN*2],cnt;
long long f[MAXN][2],d[MAXN];

void add(int u,int v,int l){
	cnt++;
	next[cnt]=head[u];
	to[cnt]=v;
	w[cnt]=l;
	head[u]=cnt;
}

void dp(int x,int fa){
	for(int i=head[x];i;i=next[i]){
		int y=to[i];
		if(y==fa)
			continue;
		dp(y,x);
		d[x]=max(d[x],d[y]+w[i]);
		f[x][0]+=f[y][0]+2*w[i];
		f[x][1]+=min(f[y][0]+w[i]-d[y],f[y][1]+w[i]*2);
	}
}

int main(){
//	freopen("portal.in","r",stdin);
//	freopen("portal.out","w",stdout);
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v,a;
		scanf("%d%d%d",&u,&v,&a);
		add(u,v,a);
		add(v,u,a);
	}
	dp(1,1);
	cout<<min(f[1][1],f[1][0]);
	return 0;
}