递归思路

//题目要求，给定一个图，注意是最小连通图(树)，删除一些边，使所有度为1的边不能到S，求最小代价
//但是我们不需要删除边，换一个思路，想象以查询的S为顶点构建一个树，我们就可以向下询问
//最小代价不就是叶子节点不能到根的最小花费吗？ 
//那么不就是选取直接将根与孩子切割或孩子下面的叶子节点不能到孩子的最小花费吗？
//那么不就可以用递归来解决吗？我们定义一个函数
//该函数接收一个顶点和其父节点（用来保证不走回头路，只往下面遍历）
//函数返回以该顶点为子树，使下面的叶子节点不能到达该顶点的最小花费
#include<iostream>
#include<vector>
using namespace std;
struct Edge
{
    int v;
    int w;
    Edge(int _v,int _w)
    {
        v=_v;
        w=_w;
    }
};
const int N=100005;
vector<vector<Edge>>adj(N,vector<Edge>());
int fun(int num,int father)
{
    long long ans=0;
    if(father==-1)
//分开是为了区分开始的情况，开始的size如果是1需要遍历孩子，因为你的根没有地方来
//而以后如果size是1，而是以后都是从上面来的，说明这个1是上面来的，下面没有了，就不用往下走了
//这种情况就是原来的树的叶子节点的父节点调用函数导致的，直接返回他的唯一的边就行了
    {
        for(auto &edge:adj[num])
        {
            ans+=min(edge.w,fun(edge.v,num));
        }
        return ans;
    }
    else
    {
        if(adj[num].size()==1)
        {
            return adj[num][0].w;
        }
        else
        {
            for(auto &edge:adj[num])
            {
                if(edge.v==father)
                {
                    continue;
                }
                ans+=min(edge.w,fun(edge.v,num));
            }
            return ans;
        }
    }
}
int main()
{
    int n,m,s;
    cin>>n>>m>>s;
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].emplace_back(v,w);
        adj[v].emplace_back(u,w);
    }
    long long ans=fun(s,-1);
    cout<<ans<<endl;
}