本文共 855 字，大约阅读时间需要 2 分钟。

额,为什么这种题会在network-flow的题单里啊…

可以跑网络流,但是明显树$dp$就好了

对于$u$的子树,要么让所有叶子节点到不了$u$

要么所有叶子节点都能到$u$(一条边都不割,割一部分一定不优)

所以$f[u]+=min(va{l}_{u->son},f[son])$

叶子节点除外

#include 
   
    using namespace std;#define int long longconst int maxn = 3e6+10;struct edge{
   	int to,nxt,w;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,int w){
   	d[++cnt] = ( edge ){
   v,head[u],w},head[u] = cnt;}int f[maxn],n,s;//f[i]表示是否能到达点ivoid dfs(int u,int fa){
   	int ans = 0,flag = 0;	for(int i=head[u];i;i=d[i].nxt )	{
   		int v = d[i].to;		if( v==fa )	continue;		dfs(v,u); flag = 1;		ans += min( d[i].w,f[v] );	}	if( flag ) f[u] = ans;}signed main(){
   	memset(f,0x3f,sizeof f );	cin >> n >> s;	for(int i=1;i
    
     > l >> r >> w;		add(l,r,w); add(r,l,w);	}	dfs(s,s);	cout << f[s];}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115442461 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！