## TLE '16 Contest 4 P4 - Christmas Tree Building

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Fax McClad and his Christmas tree (in progress).

Fax McClad, Croneria's most innovative bounty hunter, has been assigned by the Cronerian government to set up a Christmas tree.

Fax is given pieces of tree, numbered from to . There are already connections within the tree pieces, each connection has a length of and connects tree pieces and . It is guaranteed that there is no more than one path between any two tree pieces.

Fax needs to connect the tree pieces such that all of the tree pieces form a complete tree. In a complete tree, there is exactly one path between any two tree pieces. Each connection that Fax makes has a length of . Fax is allowed to choose whichever tree piece is the top.

There are two types of trees that Fax can build, which is signified by . The first type of tree has the largest height possible, so that people can see it far away. The second type of tree has the smallest height possible, since the tree might interfere with Cronerian airspace. The height of the tree is the largest distance from the top of the tree to any other tree piece.

Can you help Fax to determine what the height of his tree will be?

#### Constraints

1 5 or
2 10 or
3 15 No additional constraints or

#### Input Specification

The first line of input will contain three space-separated integers, , , and .

lines of input follow. The line will contain three space-separated integers, , , and .

#### Output Specification

Output a single integer, the maximum height of the tree if , or the minimum height of the tree if .

#### Sample Input 1

4 2 1
1 2 4
1 3 6

#### Sample Output 1

11

#### Explanation for Sample Output 1

One possible solution is to let piece be the top of the tree and connect piece to piece .

#### Sample Input 2

4 2 2
1 2 4
1 3 6

#### Sample Output 2

6

#### Explanation for Sample Output 2

One possible solution is to let piece be the top of the tree and connect piece to piece .

• commented on Jan. 20, 2022, 6:38 p.m.
• commented on Jan. 23, 2017, 10:12 p.m. edited

• commented on Dec. 24, 2016, 1:56 p.m.

This comment is hidden due to too much negative feedback. Show it anyway.

• commented on Dec. 25, 2016, 5:41 p.m.

Clearly the problems aren't the same since you solved Dreaming but not this (during the contest).

• commented on Dec. 23, 2016, 11:45 p.m.

Should tree be just the binary tree? Or any type of tree is acceptable?

• commented on Dec. 23, 2016, 11:51 p.m.

Any type of tree is acceptable.