F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist

C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
DIY | Web-DIY beta
Register new ID

# Squrirrel

Time Limit: 4000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 731    Accepted Submission(s): 235

Problem Description
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.

Input
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
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.

Sample Input
1

5

1 5 1
1 2 1
2 3 2
3 4 1

Sample Output
1 2

Source

Statistic | Submit | Discuss | Note
 Home | Top Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2023 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2023-06-10 02:46:28, Gzip enabled Administration