Thornhill Computer Club 2023 - September Contest - Problem 8

The average tree.

JoePeewee loves sticks. In fact, he loves sticks so much that he frequently observes trees to find the longest stick possible.

Each of these trees consists of multiple junction points called nodes which are connected to each to each other by branches of different lengths. There is only one path between any two nodes within a tree, this means the tree does not have any cycles. The length of a potential stick is defined as the sum of branch lengths between two nodes on the tree. These sticks are not limit to structure allowing them to bend and twist in all sorts of manners, even the trunk of a tree can be considered a stick. However, not all sticks are created equal with some being better than others. Specifically a perfectly even stick consists only of nodes with even degrees, more specifically, nodes that have an even number of branches attached to them.

JoePeewee being the most avid of stick enthusiasts considers perfectly even sticks as a separate category when trying to find the longest stick. Depending on how he feels, he might ask for the longest stick or the longest perfectly even stick of a tree. Note that the longest stick may contain the longest perfectly even stick, however, the longest perfectly even stick cannot contain the longest stick.

Given the description of a tree and the type of stick JoePeewee requests, can you help him find the longest stick of that type?

Input Specification

The first line will consist of two integers ~N~ where ~(2 \le N \le 10000)~ representing the number of nodes within the tree and ~T~ where ~(T == 1 || T == 2)~ representing the type of request. Type 1 represents a request for the longest stick, Type 2 represents a request for the longest perfectly even stick.
The next ~N - 1~ lines will consist of 3 integers ~a~ where ~(1 \le a \le N)~, ~b~ where ~(1 \le b \le N)~, and ~l~~ (1 \le l \le N)~ representing the starting node, ending node, and length of the branch that connects those two nodes.
It is guaranteed that all nodes are part of the same tree.

Output Specification

On a single line, output the length of the stick of the requested type.

Subtasks

Subtask 1 [20%]:
JoePeewee will only make type 1 requests.
~n \le 100~

Subtask 2 [30%]:
~n \le 100~

Subtask 3 [20%]:
JoePeewee will only make type 1 requests.

Subtask 4 [30%]:
No further constraints.

Sample Input 1

10 1
2 9 3
3 1 6
7 1 3
8 1 4
1 6 6
6 5 8
5 4 1
9 4 2
4 10 7

Sample Output 1

28

Explanation of Sample Output 1

JoePeewee requests for the longest stick, not the longest perfectly even stick.
The longest stick that can be formed within this tree connects nodes 10 and 3 with a total length of 28.

Sample Input 2

10 2
3 7 4
4 2 1
7 5 6
5 2 3
2 1 2
8 6 7
6 9 2
9 1 5
1 10 3

Sample Output 2

6

Explanation of Sample Output 2

Here, JoePeewee requests for the longest perfectly even stick.
Nodes 5, 6, 7, and 9 are the only perfectly even nodes.
The only perfectly even sticks that can be formed using these nodes connect nodes 5 to 7 with a length of 6 and nodes 6 to 9 with a length of 2.
Out of these two sticks, the stick with length 6 is the longest.

Sample Input 3

23 2
3 7 4
4 2 1
7 5 6
5 2 3
2 1 2
8 6 7
6 9 2
9 1 5
1 10 3
1 11 5
2 12 4
9 13 2
5 14 4
5 15 8
9 16 4
11 17 8
11 18 9
11 19 4
2 20 7
19 21 1
2 22 9
4 23 2

Sample Output 3

20

Explanation of Sample Output 3

The longest perfectly even stick connects nodes 7 to 19 with a total length of 20.