DMOPC '21 Contest 3 P5 - Crowded Travels

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

You got the once-in-a-lifetime chance to go to Tokyo right now! As Tokyo is a large city, you've split it into N areas connected by N-1 roads such that it is possible to travel from any area to any other using these roads. The i-th road connects areas a_i and b_i, and it takes c_i seconds to travel it in either direction. The target attraction of your trip is the maid café located in area 1.

In order to properly plan out your trip, you need to estimate how long it would take to go from certain areas to area 1. Initially, all of the areas are uncrowded, and you may choose any neighbouring area as your next destination in an uncrowded area. However, Tokyo is a very busy city, so some areas may become crowded as the day progresses! In any crowded area you have no control over where you are headed, and will pick a neighbouring area uniformly at random as your next destination if you choose to leave the current area.

To ensure the success of your trip, write a program that supports Q of the following events:

  • 1 u: A previously uncrowded area u becomes crowded.
  • 2 u: You need to determine the minimum possible expected travel time from area u to area 1 in the current state of all the areas.


1 \le N, Q \le 3 \times 10^5

1 \le a_i, b_i \le N

1 \le c_i \le 10^6

For all events, 1 \le u \le N.

Subtask 1 [30%]

All type 1 events occur before all type 2 events.

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains 2 integers N and Q.

The next N-1 lines each contain 3 integers a_i, b_i, and c_i.

The next Q lines each describe an event.

Output Specification

For each type 2 event, output the answer (in seconds) on a new line.

Sample Input

7 7
1 2 4
1 3 3
2 4 2
3 5 1
3 6 3
6 7 2
2 4
1 3
1 6
1 4
2 7
1 1
2 1

Sample Output



There are no comments at the moment.