当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6613:Squrirrel

题目描述
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\leq T\leq 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\leq n\leq 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\leq u,v\leq n,1\leq w\leq 200)$.

It is guaranteed that $(1\leq ∑n\leq 2,000,000)$.


$(1\leq T \leq 20)$

$(1\leq n\leq 200,000)$

$(1\leq u,v\leq n,1\leq w\leq 200)$

$(1\leq ∑n\leq 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
来自杭电HDUOJ的附加信息
Recommend chendu

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6613

最后修改于 2020-10-25T23:32:48+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
4000/4000MS(Java/Others) 65536/65536K(Java/Others)