This page is still under construction.

Parts of this page are still being built. What you see may change.

Tree Trunk and Branches

Interview

Time limit2.5sMemory limit1024 MB

Summary
Given a rooted weighted tree, find the giga node (first node from the root with at least two children, or the single leaf), then output the trunk length and the longest branch length from the giga node to a leaf.
Level

Medium5 of 10

Topics
Tree, DFS, Implementation, Recursion
Solved
No attempts yet

Problem

Micro, a civil servant at the city office, was ordered by his section chief to determine the length of the trunk and the length of the longest branch of a tree in the city.

Micro decided that using the tree data structure he learned at ICPC Sinchon Winter Algorithm Camp would make this task easier.

Micro defined the giga node to classify the trunk and branches of a tree.

The giga node is the first node with 22 or more children when traversing from the root node. The name comes from shortening trunk and branch to giga. In the figure above, the giga node is node 44.

However, as in the figure above, when there is only 11 leaf node, the leaf node is also the giga node.

Also, as in the figure above, the root node can also be the giga node.

  • The trunk of the tree is from the root node to the giga node. In the figure above, the trunk is 1−2−3−41-2-3-4.
    The length of the trunk is the sum of the edge lengths of the trunk, 1+2+3=61 + 2 + 3 = 6.
  • A branch of the tree is from the giga node to any leaf node. In the figure above, the branches are 4−5−6−74-5-6-7, 4−5−84-5-8, 4−94-9, 4−10−114-10-11, and 4−10−124-10-12, 55 in total.
    The length of a branch is the sum of the edge lengths of the branch. Fortunately, only the length of the longest branch needs to be recorded. The branch 4−10−124-10-12 is the longest branch with an edge length sum of 3+3=63 + 3 = 6.

Micro transferred the city's tree into a tree data structure. But the section chief gave Micro another task! Let us measure the length of the trunk and the longest branch of the tree on behalf of the very busy Micro.

Input

The first line gives the number of nodes NN(1≤N≤200 0001 \le N \le 200\,000) and the number of the root node RR(1≤R≤N1 \le R \le N).

After that, N−1N-1 lines each give three integers aa, bb, dd(1≤a,b≤N1 \le a, b \le N, a≠ba \ne b). This means that node aa and node bb are connected and the length of this edge is dd(1≤d≤1 0001 \le d \le 1\,000). Nodes are numbered with integers from 11 to NN, and the same edge is not given more than once.

Graphs that are not trees are not given as input.

Output

Print the length of the trunk of the tree and the length of the longest branch.

Examples4

  1. Example 1

    Input
    12 1
1 2 1
2 3 2
3 4 3
4 5 1
5 6 2
6 7 1
5 8 1
4 9 2
4 10 3
10 11 1
10 12 3
    Expected output
    6 6

  2. Example 2

    Input
    9 1
1 2 5
2 3 4
3 4 2
2 5 5
1 6 8
1 7 6
7 8 7
7 9 1
    Expected output
    0 13

  3. Example 3

    Input
    4 1
1 2 100
2 3 10
3 4 1
    Expected output
    111 0

  4. Example 4

    Input
    1 1
    Expected output
    0 0