题干：

链接：https://ac.nowcoder.com/acm/contest/188/C
来源：牛客网
 

小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

备注:

1 ≤ n ≤ 50000 , 1 ≤ w ≤ 2147483647

解题报告：

  和   牛客369的C一样的思维。

AC代码：

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#define ll long long
using namespace std;
const int MAX = 6e5 + 5 ; 
const int INF = 0x3f3f3f3f;
struct Node {
	int to;
	int w;
	int ne;
} e[MAX];
struct point {
	int pos,c;
	point(){}
	point(int pos,int c):pos(pos),c(c){}
 
};
int n;
int head[MAX];
int cnt = 0 ;
bool vis[MAX];
void init() {
	cnt = 0;
	memset(head,-1,sizeof(head));
}
void add(int u,int v,int w) {
	e[cnt].to = v;
	e[cnt].w = w;
	e[cnt].ne = head[u];
	head[u] = cnt;
	cnt++;  
} 
 
int bfs(int x,int &w) {
	queue <point> q;
	int maxx = 0;
	int retp = x ;//返回的点坐标 
	memset(vis,0,sizeof(vis) );
	q.push(point(x,0));vis[x] = 1;
	point now;
	while(q.size() ) {
		point cur = q.front();
		q.pop();
		for(int i = head[cur.pos]; i!=-1; i=e[i].ne) {
			if(vis[e[i].to]) continue;
			vis[e[i].to] = 1;
			now.pos = e[i].to;
			now.c = cur.c + e[i].w;
			if(now.c>maxx) {
				maxx = now.c;
				retp = now.pos;
			}
			q.push(now);
		}
		//w = maxx;
		
	}
	w = maxx;
	return retp;
}
int main()
{
    int x;
	cin>>n>>x;
	init();
	int u,v,w;
	ll sum = 0;
	for(int i = 1; i<=n-1; i++) {
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
		sum += w;
	}
	int ans1 = 0,ans2 = 0;
	u = bfs(x,ans1);
	//printf("ans2 = %d\n",ans2);
	printf("%lld\n",1LL*ans1 + (sum-ans1)*2);
	return 0 ;
}