链接：https://ac.nowcoder.com/acm/problem/18947
来源：牛客网

题目描述
小w不会离散数学，所以她van的图论游戏是送分的
小w有一张n个点n-1条边的无向联通图,每个点编号为1~n,每条边都有一个长度
小w现在在点x上
她想知道从点x出发经过每个点至少一次，最少需要走多少路
输入描述:
第一行两个整数 n,x,代表点数,和小w所处的位置
第二到第n行,每行三个整数 u,v,w,表示u和v之间有一条长为w的道路
输出描述:
一个数表示答案
示例1
输入
复制
3 1
1 2 1
2 3 1
输出
复制
2

大部分路都要走两边，只有最多的一条路不需要走 找到这条路就可以了

#include<iostream>                            //https://ac.nowcoder.com/acm/problem/18947
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
#define ll long long 
int n,x,sum=0;
ll cent = 0;                        //怕爆所以开ll 
vector<int>v[N];                    //两个vevtor，一个对于每个点联通的节点，一个存对应的路的长度 
vector<int>w[N]; 
void dfs(int now,int fa,ll cen)
{
    for(int i=0;i<v[now].size();i++)
    {
        if(v[now][i]==fa) continue;                        //当等于时 ， 本来就是双向连通图， 自己的子节点
        dfs(v[now][i],now,cen+w[now][i]);                // 中也就相当于包括自己的父节点 ，所以为了避免搜索时搜索回去，所以需要写if 
    }
    if(now!=x&&v[now].size()==1)                        //相当于跳出条件吧，当size等于 1时，也就是到达了末尾，除了返回上一级
                                                        //也没有别的，cent负责记录最大的一条路，这条路在题中只走一次 
    {
        cent = max(cent,cen);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>x;
    for(int i=0;i<n-1;i++)
    {
        int t1,t2,c;
        cin>>t1>>t2>>c;
        v[t1].push_back(t2);            //对应下去，因为是无向的，所以互相存 
        v[t2].push_back(t1);
        w[t1].push_back(c);
        w[t2].push_back(c);
        sum+=c;
    }
    dfs(x,-1,0);
    cout<<sum*2-cent<<endl;                //大部分路都要走两边，只有最多的一条路不需要走 
    return 0;    
}