TCCC' 23 Dec P4 - The Bronze Christmas Tree

View as PDF

Submit solution

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

Problem type

With 2.9 million beautiful grins on 2.9 million proud elves standing at the front gates of Santa's present factory, What was once a place of terror and monotonous labour is now a gold mine of glorious presents ripe for the taking by these awestruck elves. The alpha elf, Stanley, begins his howl. Slowly but surely as more and more elves start contributing to the howl, the whole North Pole is covered in song of brotherhood and of the pack. All 2.9 million elves have turned into wereelves.

Foreign security at Santa's factory was as a little relaxed since there are only so many people who know where the factory is located (and much less able to escape this factory of a prison). Resistance to the 2.9 million elves was always going to be futile. Now, with all the guards brutally beaten into sleep, the elves now need to finish the heist.

Luckily, there are loads of presents that are already made in preparation for Christmas, ripe for burglary [fountain diving (theft)]. Getting all the presents won't be an issue for the elves due to Santa's organizational skills. Santa is smart, he knows that if he wants to deliver presents to all 2 billion freeloaders (children) across the globe, he will need a way to organize that many presents. The elves, entering the massive factory building is blinded by the warm orange glow of Santa's choice of organizational structure, a huge bronze pine tree that just so happens to also follow the definition of a tree in graph theory (50elephants has already run out of spiky animals for his spiky metallic animal series).

The massive bronze tree lies on the ground with each end node of the having a present tree. It takes an elf w_i minutes to travel from a node to an adjacent node. Of course, the elves won't simply climb the tree from the root. Instead, they will launch all of themselves onto a single landing node on the tree. With 2.9 million elves at their disposal, they will quickly flood the tree in every direction from the landing node, guaranteeing that an elf will grab each present along all paths of the tree and reconvene back at the landing node.

The elves are fast, but would like if they could get all the presents as fast as they can before security catches them. Can you determine which root node will minimize the time they need to get all the presents from the Bronze Christmas Tree?

Python users are recommended to use PyPy3

Input Specification

The first line of input will contain an integer N (2 \le N \le 10^5) the number of nodes.
The next N - 1 lines will contain 3 integers u_i, v_i, and w_i (1 \le  w \le 10^4) representing a bidirectional edge between nodes u_i and v_i with a distance of w_i. There will be at most 1 edge between two nodes. u_i and v_i are pairwise distinct.

Output Specification

On the first line, an integer representing the shortest time in minutes to get all the presents.
For all nodes that result in the shortest time to get all presents separated by a space, a line containing an integer representing that node.


Subtask 1 [10%]:

  • N \le 100

Subtask 2 [20%]:

  • N \le 1000

Subtask 3 [70%]:

  • No further constraints

Sample Input 1

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

Sample Output 1


Explanation for Sample Output 1

Landing on node 4 is optimal.
Walking to node 1 from node 4 and back would take 12 minutes.
Walking to node 2 from node 4 and back would take 10 minutes.
Walking to node 3 from node 4 and back would take 4 minutes.
Walking to node 5 from node 4 and back would take 30 minutes.
The longest out of these times is 30 minutes.
There is no other landing node that takes a shorter amount of time.

Sample Input 2

1 3 3
3 5 2
4 3 7
2 4 14
2 6 2
6 7 8
6 8 1

Sample Output 2


Explanation For Sample Output 2

By launching themselves onto node 2, the elves can run to every node of the tree and back within 48 minutes, the shortest time possible.
The same can be done if they launched onto node 4. (If there are multiple answers for the best node, output them in any order on two separated lines)


There are no comments at the moment.