3873: Squrirrel
内存限制：128 MB
时间限制：4.000 S
评测方式：文本比较
命题人：
提交：3
解决：1
题目描述
Master magician `eom` is searching for his naughty squirrel. The squirrel hides at a node of a tree, while its owner `eom` has no idea which node it hides at. As a magician, `eom` can choose a node and release many magical creatures to search his squirrel in all directions at the speed of 1. Besides, he can choose a pair of adjacent nodes on the tree and reduce the distance between them to 0 before releasing magical creatures. Please help him to find the start node to release magical creatures, so that `eom` can find his squirrel in the shortest time even in the worst condition. Note that `eom` is full of wisdom, so that he can optimally make decision to reduce the distance after the start node is determined.
输入
The first line contains a integer T(1≤T≤20), indicating there are T test cases followed.
For each test case, the first line contains one integers n: the number of nodes of the tree(1≤n≤200,000).
In the following n−1 lines, each line has three integers u,v and w, indicating there exists a line between node u and v, which length equals to w(1≤u,v≤n,1≤w≤200).
It is guaranteed that (1≤∑n≤2,000,000).
(1≤T≤20)
(1≤n≤200,000)
(1≤u,v≤n,1≤w≤200)
(1≤∑n≤2000000)
For each test case, the first line contains one integers n: the number of nodes of the tree(1≤n≤200,000).
In the following n−1 lines, each line has three integers u,v and w, indicating there exists a line between node u and v, which length equals to w(1≤u,v≤n,1≤w≤200).
It is guaranteed that (1≤∑n≤2,000,000).
(1≤T≤20)
(1≤n≤200,000)
(1≤u,v≤n,1≤w≤200)
(1≤∑n≤2000000)
输出
Output two integers. The first one is the index of the start node you should choose and the second one is the least time required in the worst condition. If there are multiple possible ways to choose the start node to minimize the time, the index of start node chosen should be minimum.
样例输入 复制
1
5
1 5 1
1 2 1
2 3 2
3 4 1样例输出 复制
1 2