Rinne Loves Edges

题意:把输入的S点做为根节点,然后把输入的图看成一棵树,使的树中的所有叶子节点与跟节点都不存在一条通路

为什么说是可以看成树, 因为n个节点m条边的无向连通图,又因为M条边,M+1个节点,emmm...数据结构教材上树的定义魔改后可以这样看
题解:树形DP(今天刚学,逃..........)
什么是树形DP,指在树这种数据结构上进行的DP:给出一棵树,要求最少的代价(或取得最大的收益)完成给定的操作,
emmm...那个跑题了,拉回来
设第 个点为根节点,并设其最终结果为 ,那么 是否就等于他所有的直接到达的孩子节点所的 与 取最小的求和

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+10;
vector<ll>sc[maxn];
vector<ll>v[maxn];
ll n,m,s;
ll dfs(ll u,ll v1,ll c3)
{
    if(sc[u].size()==1&v1!=0)
    {

        return v[u][0];
    }
  ll ans=0;
    int len=sc[u].size();
    for(int i=0; i<len; i++)
    {if(sc[u][i]!=v1)
        ans+=dfs(sc[u][i],u,v[u][i]);

    }
    return min(ans,c3);

}
int main()
{

    cin>>n>>m>>s;
    for(int i=0; i<m; i++)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        sc[a].push_back(b);
        sc[b].push_back(a);
        v[a].push_back(c);
        v[b].push_back(c);
    }
    cout<<dfs(s,0, (1ll << 63) - 1);

}