Rinne Loves Edges【牛客tracker 每日一题】
Rinne Loves Edges
时间限制：1秒 空间限制：128M
知识点：思维题
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
R i n n e RinneRinne最近了解了如何快速维护可支持插入边删除边的图，并且高效的回答一下奇妙的询问。
她现在拿到了一个n nn个节点m mm条边的无向连通图，每条边有一个边权w i w_iwi
现在她想玩一个游戏：选取一个 “重要点”S SS，然后选择性删除一些边，使得原图中所有除S SS之外度为1 11的点都不能到达S SS。
定义删除一条边的代价为这条边的边权，现在R i n n e RinneRinne想知道完成这个游戏的最小的代价，这样她就能轻松到达r k 1 rk1rk1了！作为回报，她会让你的排名上升一定的数量。
输入描述：
第一行三个整数N , M , S N,M,SN,M,S，意义如「题目描述」所述。
接下来M MM行，每行三个整数u , v , w u,v,wu,v,w代表点u uu到点v vv之间有一条长度为w ww的无向边。
输出描述：
一个整数表示答案。
示例1
输入：
4 3 1 1 2 1 1 3 1 1 4 1输出：
3说明：
需要使得点2 , 3 , 4 2,3,42,3,4不能到达点1 11，显然只能删除所有的边，答案为3 33
示例2
输入：
4 3 1 1 2 3 2 3 1 3 4 2输出：
1说明：
需要使得点4 44不能到达点1 11，显然删除边2 ↔ 3 2↔32↔3是最优的。
备注：
2 ≤ S ≤ N ≤ 10 5 , M = N − 1 2≤S≤N≤10^5,M=N−12≤S≤N≤105,M=N−1，保证答案在C + + l o n g l o n g C++ \ long \ longC++longlong范围内。
解题思路
本题核心是通过树形DP+DFS求解最小删除代价，因题目中M = N − 1 M=N-1M=N−1且图连通，本质为以S SS为根的树：首先明确目标是切断所有叶子节点（度为1 11且非S SS）到S SS的路径，最小化删除边的代价；定义d p [ x ] dp[x]dp[x]为切断以x xx为根的子树中所有叶子节点到x xx路径的最小代价。D F S DFSDFS遍历树时，若x xx是叶子节点（非S SS），则d p [ x ] dp[x]dp[x]设为无穷大（必须删除连接它的边）；否则对每个子节点v vv，d p [ x ] dp[x]dp[x]累加m i n ( d p [ v ] , w ) min(dp[v], w)min(dp[v],w)（选择切断子树内部路径或直接删除x − v x-vx−v边的较小代价）。最终d p [ S ] dp[S]dp[S]即为切断所有叶子到S SS路径的最小代价。该方法时间复杂度O ( N ) O(N)O(N)，适配N ≤ 1 e 5 N≤1e5N≤1e5的规模，通过树形D P DPDP精准计算最优删除策略的代价。
总结
- 核心逻辑：将问题转化为树形D P DPDP，每个节点选择切断子树内部或删除当前边的最小代价。
- 关键操作：D F S DFSDFS遍历树，叶子节点设为无穷大，非叶子节点累加子节点的最小代价。
- 结果输出：根节点S SS的d p dpdp值即为切断所有叶子路径的最小删除代价。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vt;typedefpair<ll,ll>pll;constll N=1e5+10;constll p=1e4+7;constll INF=1e18;vector<pll>d[N];ll dp[N],vis[N];voiddfs(ll x){vis[x]=1;ll op=1;dp[x]=0;for(auto&e:d[x]){ll v=e.first;ll w=e.second;if(!vis[v]){op=0;dfs(v);dp[x]+=min(dp[v],w);}}if(op)dp[x]=INF;}intmain(){ll n,m,s;cin>>n>>m>>s;while(m--){ll u,v,w;cin>>u>>v>>w;d[u].emplace_back(v,w);d[v].emplace_back(u,w);}dfs(s);cout<<dp[s]<<endl;return0;}