LG1131 「ZJOI2007」时态同步树形DP

问题描述

题解

正难则反，把从一个点出发到叶子结点看做从叶子结点走到那个点。

DP方程很显然。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

#define int long long

void read(int &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();

	if(ch=='-') ch=getchar(),fh=-1;

	else fh=1;

	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	x*=fh;

}

const int maxn=500000+7;

int n,mx[maxn],opt[maxn],S,dis[maxn];

int Head[maxn],to[maxn*2],tot=1,Next[maxn*2],w[maxn*2];

int ans;

void add(int x,int y,int z){

	to[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=z;

} 

void dfs(int x,int f){

	for(int i=Head[x];i;i=Next[i]){

		int y=to[i];

		if(y==f) continue;dfs(y,x);

	}

	for(int i=Head[x];i;i=Next[i]){

		int y=to[i];

		if(y==f) continue;

		mx[x]=max(mx[x],w[i]);

	}

	for(int i=Head[x];i;i=Next[i]){

		int y=to[i];

		if(y==f) continue;

		ans=ans+mx[x]-w[i];

	}

	for(int i=Head[f];i;i=Next[i]){

		int y=to[i];

		if(y==x) w[i]+=mx[x];

	}

}

signed main(){

	read(n);read(S);

	for(int i=1,x,y,z;i<n;i++){

		read(x);read(y);read(z);

		add(x,y,z);add(y,x,z);

	}

	dfs(S,0);

	printf("%lld\n",ans);

	return 0;

}

巴特西

LG1131 「ZJOI2007」时态同步树形DP

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章

巴特西

LG1131 「ZJOI2007」时态同步 树形DP

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章

LG1131 「ZJOI2007」时态同步树形DP