自动搬运

查看原文

来自洛谷，原作者为

	_louhc 已故 o（x（工）x）o

搬运于2025-08-24 21:54:16，当前版本为作者最后更新于2018-12-18 19:21:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P3931 SAC E#1 - 一道难题 Tree

写在前面

lovny(YKJ):用树形DP呀？

Venus(LYT):还在做网络流？

。。。

没必要！完全没必要！这道题DFS就够了！

思路

很明显，要使一个叶子节点到不了祖先，有两种选择：

他的某个祖先到不了根节点

它父亲->它 删了

然后我们可以遍历一遍树。

DFS( x, fa ) = $\Sigma$min(DFS( i, x ) ( 存在边x->i), val(x->i) )

fa是为了避免搜到父亲节点。

若x为叶子节点，直接返回INF

也就是说，要么断开x->i让i到不了根节点，下面就不用再删边了，要么让i到的了根节点，在下面某处再断开。

他没说c的范围，保险起见开long long

代码很短。。。真的很短。。。

代码

#include<bits/stdc++.h>
using namespace std;
#define open(s) freopen( s".in", "r", stdin ), freopen( s".out", "w", stdout )
#define MAXN 100005
#define MAXM 200005
#define LL long long

int n, S;
int hd[MAXN], to[MAXM], nxt[MAXM], tot(1);
LL val[MAXM];

void Add( int x, int y, int z ){
	nxt[++tot] = hd[x]; hd[x] = tot; val[tot] = z; to[tot] = y;
	nxt[++tot] = hd[y]; hd[y] = tot; val[tot] = z; to[tot] = x;
}

LL DFS( int x, int fa ){
	LL ans(0); bool flg(0);
	for ( int i = hd[x]; i; i = nxt[i] )
		if ( to[i] != fa ) ans += min( DFS( to[i], x ), val[i] ), flg = 1;
	if ( !flg ) return LONG_LONG_MAX;
	return ans;
}

int main(){
	scanf( "%d%d", &n, &S );
	for ( int i = 1; i < n; ++i ){
		int x, y; LL z;
		scanf( "%d%d%lld", &x, &y, &z );
		Add( x, y, z );
	}
	printf( "%lld\n", DFS( S, S ) );
	return 0;
}