雨巨DP专题：第二题（Rinne Loves Edges）树形DP

题意

删除一些边，代码为删除边权的和,保证除s以外，所有度数为1（叶子结点）的结点不可达s。

思路

s为根，进行dfs
$dp[u]=min(inf,\sum_{v∈u->son}{min(dis(u,v),dp[v])})$
维护就OK

题目链接

//#pragma GCC optimize(2)
//#pragma GCC target ("sse4")
#include<bits/stdc++.h>
//typedef long long ll;
#define ull unsigned long long
#define int long long
#define F first
#define S second
#define endl "\n"//<<flush
#define eps 1e-6
#define base 131
#define lowbit(x) (x&(-x))
#define db double
#define PI acos(-1.0)
#define inf 0x3f3f3f3f
#define MAXN 0x7fffffff
#define INF 0x3f3f3f3f3f3f3f3f
#define ferma(a,b) pow(a,b-2)
#define mod(x) (x%mod+mod)%mod
#define pb push_back
#define decimal(x) cout << fixed << setprecision(x);
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define memset(a,b) memset(a,b,sizeof(a));
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
#ifndef ONLINE_JUDGE
#include "local.h"
#endif
template<typename T> inline T fetch(){T ret;cin >> ret;return ret;}
template<typename T> inline vector<T> fetch_vec(int sz){vector<T> ret(sz);for(auto& it: ret)cin >> it;return ret;}
template<typename T> inline void makeUnique(vector<T>& v){sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());}
void file()
{
#ifdef ONLINE_JUDGE
#elsefreopen("D:/LSNU/codeforces/duipai/data.txt","r",stdin);// freopen("D:/LSNU/codeforces/duipai/WA.txt","w",stdout);
#endif
}
const int N=1e5+5;
struct node
{int v,w,next;
}s[N<<1];
int head[N],cnt=0,dp[N];
void add(int u,int v,int w)
{s[++cnt].next=head[u];s[cnt].v=v;s[cnt].w=w;head[u]=cnt;
}
void dfs(int u,int fat)
{int sum=0,flag=1;for(int i=head[u];i;i=s[i].next){int v=s[i].v,w=s[i].w;if(v==fat)continue;flag=0;dp[v]=w;dfs(v,u);sum+=dp[v];}if(flag)sum=INF;dp[u]=min(dp[u],sum);
}
signed main()
{IOS;file();int n,m,s;cin>>n>>m>>s;memset(dp,0x3f);while(m--){int u,v,w;cin>>u>>v>>w;add(u,v,w);add(v,u,w);}dfs(s,0);cout<<dp[s]<<endl;return 0;
}