题目描述

有一个村庄居住着 $n$ 个村民，有 $n-1$ 条路径使得这 $n$ 个村民的家联通，第 $i$ 条路径的长度为 $c_i$。现在村长希望在某个村民家中召开一场会议，村长希望最远的村民到会议地点的距离最小，那么村长应该要把会议地点设置在哪个村民的家中？最远的村民到会议地点的距离值是多少呢？若有多个节点都满足条件，则选择节点编号最小的那个点。

输入格式

第一行，一个数 $n$，表示有 $n$ 个村民。
接下来 $n−1$ 行，每行三个数字 $a_i,b_i,c_i$，表示村民 $ai$ 的家和村民 $bi$ 的家之间存在一条 $ci$ 长的路径。

输出格式

一行输出两个数字 $x$ 和 $y$ ，表示村长将会在村民 $x$ 家中举办会议。最远的村民到会议地点的距离值为 $y$。

样例输入

4
1 2 3
2 3 4
3 4 5

样例输出

3 7

数据范围

$1 \le n \le 5 \times 10^4,c_i\le 1000$

代码

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inline")
#define hh putchar('\n')
#define kg putchar(' ')
#define debug puts("debug")
//#define int long long
//#define int __int128
namespace quickread{
	template<typename T> void read(T &x){
		x=0;char c=getchar();T neg=0;
		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
		if(neg) x=(~x)+1;
	}
	template<typename T> void write(T x){
		if(x<0) putchar('-'),x=~x+1;
		if(x>9) write(x/10);
		putchar(x%10^48);
	}
	inline string readstr(){
    	char ch=getchar();string str="";
		while(!(ch>='0'&&ch<='9')&&!(ch>='a'&&ch<='z')&&!(ch>='A'&&ch<='Z')) ch=getchar();
		while((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){str+=ch;ch=getchar();}
		return str;
	}
	inline char readchar(){
		char ch=getchar();
		while(!(ch>='0'&&ch<='9')&&!(ch>='a'&&ch<='z')&&!(ch>='A'&&ch<='Z')) ch=getchar();
		return ch;
	}
}
using namespace quickread;
const int N=1e6+10,inf=2147483647;
int n,d1[N],d2[N],pos[N],up[N],ans=inf,k;
struct edge{int v,w;};
vector<edge> tree[N];
struct node{int val,x;};
bool operator < (const node& A,const node& B){return A.x<B.x;}
void dfs1(int u,int f){
    for(edge to:tree[u]){
        int v=to.v,w=to.w;
        if(v!=f){
            dfs1(v,u);
            w+=d1[v];
            if(w>d1[u]) d1[u]=w,pos[u]=v;
            else if(w>d2[u]) d2[u]=w;
        }
    }
}
void dfs2(int u,int f){
    for(edge to:tree[u]){
        int v=to.v,w=to.w;
        if(v!=f){
            if(pos[u]==v) up[v]=d2[u]+w;
            else up[v]=d1[u]+w;
            up[v]=max(up[u]+w,up[v]);
            dfs2(v,u);
        }
    }
}
signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
    read(n);
    for(int i=1;i<n;i++){
        int u,v,w;
        read(u),read(v),read(w);
        tree[u].push_back(edge{v,w});
        tree[v].push_back(edge{u,w});
    }
    dfs1(1,0),dfs2(1,0);
    for(int u=1;u<=n;u++){
        int maxn=max(up[u],d1[u]);
        if(maxn<ans) ans=maxn,k=u;
        else if(maxn==ans&&u<k) u=k;
    }
    write(k),kg,write(ans);
	return 0;
}

/*
7
1 2 3
1 5 3
2 3 4
2 6 4
3 4 5
3 7 5
*/