TLE '16 Contest 4 P4 - Christmas Tree Building - Olympiads Online Judge

TLE '16 Contest 4 P4 - Christmas Tree Building

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

ZQFMGB12

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 $N$ $N$ pieces of tree, numbered from $1$ $1$ to $N$ $N$ . There are already $M$ $M$ connections within the tree pieces, each connection $i$ $i$ has a length of $l_i$ $l_{i}$ and connects tree pieces $u_i$ $u_{i}$ and $v_i$ $v_{i}$ . 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 $1$ $1$ . 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 $Q$ $Q$ . The first type of tree $(Q = 1)$ $(Q = 1)$ has the largest height possible, so that people can see it far away. The second type of tree $(Q = 2)$ $(Q = 2)$ 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

$2 \le N$ $2 \leq N$

$0 \le M \le N-1$ $0 \leq M \leq N - 1$

$1 \le l_i \le 10^6$ $1 \leq l_{i} \leq 10^{6}$

Subtask	Points	$N$ $N$	$M$ $M$	$Q$ $Q$
1	5	$N \le 100$ $N \leq 100$	$M = 1$ $M = 1$	$Q = 1$ $Q = 1$ or $2$ $2$
2	10	$N \le 100$ $N \leq 100$	$M = N-1$ $M = N - 1$	$Q = 1$ $Q = 1$ or $2$ $2$
3	15	$N \le 100$ $N \leq 100$	No additional constraints	$Q = 1$ $Q = 1$ or $2$ $2$
4	25	$N \le 10^5$ $N \leq 10^{5}$	No additional constraints	$Q = 1$ $Q = 1$
5	45	$N \le 10^5$ $N \leq 10^{5}$	No additional constraints	$Q = 2$ $Q = 2$

Input Specification

The first line of input will contain three space-separated integers, $N$ $N$ , $M$ $M$ , and $Q$ $Q$ .

$M$ $M$ lines of input follow. The $i^\text{th}$ $i^{th}$ line will contain three space-separated integers, $u_i$ $u_{i}$ , $v_i$ $v_{i}$ , and $l_i$ $l_{i}$ .

Output Specification

Output a single integer, the maximum height of the tree if $Q = 1$ $Q = 1$ , or the minimum height of the tree if $Q = 2$ $Q = 2$ .

Sample Input 1

Copy

4 2 1
1 2 4
1 3 6

Sample Output 1

Copy

Explanation for Sample Output 1

$\text{[math]}$

One possible solution is to let piece $2$ $2$ be the top of the tree and connect piece $4$ $4$ to piece $3$ $3$ .

Sample Input 2

Copy

4 2 2
1 2 4
1 3 6

Sample Output 2

Copy

Explanation for Sample Output 2

$\text{[math]}$

One possible solution is to let piece $1$ $1$ be the top of the tree and connect piece $4$ $4$ to piece $2$ $2$ .

Comments

2

RAiNcalleER commented on Jan. 20, 2022, 6:38 p.m.

https://codeforces.com/blog/entry/17974

33

Kirito commented on Jan. 23, 2017, 10:12 p.m. ← edited →

-13

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

stop blatantly stealing problems

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

26

thomas0115 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).

2

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

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

7

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

Any type of tree is acceptable.