题目描述

Rinne 最近了解了如何快速维护可支持插入边删除边的图，并且高效的回答一下奇妙的询问。
她现在拿到了一个 n 个节点 m 条边的无向连通图，每条边有一个边权 w
现在她想玩一个游戏：选取一个 “重要点” S，然后选择性删除一些边，使得原图中所有除 S 之外度为 1 的点都不能到达 S。
定义删除一条边的代价为这条边的边权，现在 Rinne 想知道完成这个游戏的最小的代价，这样她就能轻松到达 rk1 了！作为回报，她会让你的排名上升一定的数量。

题解

m=n-1并且图联通，那么这个图就是一棵树，所以本题可转换为，以S为根的树，求所有叶子节点与S不连通的最小代价。
那么我们可以将每条边的边权转换为点权(架空根节点S，所有边权指向深度较大的那个点)，然后代价就变成每颗子树的代价和，或者是当前节点的权值，两者取最小的就可以了！像树形dp那样~

代码

#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 2e6 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
//const int mod = 998244353;
//LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}

//head

struct Edge{
    int to,w,next;
}edge[maxn];
int tot,head[maxn];
void add(LL u,LL v,LL w){
     edge[++tot]={v,w,head[u]};
     head[u]=tot;
}

LL n,m,s,a[maxn],dp[maxn];
VI G[maxn];

void dfs(int u,int fa,LL w){
     dp[u]=w;
     LL mi=0;
     for(int i=head[u];i;i=edge[i].next){
        LL v=edge[i].to,w=edge[i].w;
        if(v==fa) continue;
        dfs(v,u,w);
        mi+=dp[v];
     }
     if(mi)
     dp[u]=min(dp[u],mi);
}

int main(){
     scanf("%lld%lld%lld",&n,&m,&s);
     for(LL i=1,u,v,w;i<n;i++){
        scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w);add(v,u,w);
     }
     dfs(s,-1,inf);
     printf("%lld\n",dp[s]);
}