Train Tracks
Contest: Codeforces Round 639 (Div. 1)
Difficulty rating: 3100
Tags: data structures, trees

That's right. I'm a Purdue student, and I shamelessly wrote a problem about trains.

There are $$$n$$$ stations and $$$m$$$ trains. The stations are connected by $$$n-1$$$ one-directional railroads that form a tree rooted at station $$$1$$$. All railroads are pointed in the direction from the root station $$$1$$$ to the leaves. A railroad connects a station $$$u$$$ to a station $$$v$$$, and has a distance $$$d$$$, meaning it takes $$$d$$$ time to travel from $$$u$$$ to $$$v$$$. Each station with at least one outgoing railroad has a switch that determines the child station an incoming train will be directed toward. For example, it might look like this:

Here, stations $$$1$$$ and $$$3$$$ have switches directed toward stations $$$2$$$ and $$$4$$$, respectively.

Initially, no trains are at any station. Train $$$i$$$ will enter station $$$1$$$ at time $$$t_i$$$. Every unit of time, starting at time $$$1$$$, the following two steps happen:

1. You can switch at most one station to point to a different child station. A switch change takes effect before step $$$2$$$.
2. For every train that is on a station $$$u$$$, it is directed toward the station $$$v$$$ indicated by $$$u$$$'s switch. So, if the railroad from $$$u$$$ to $$$v$$$ has distance $$$d$$$, the train will enter station $$$v$$$ in $$$d$$$ units of time from now.

Every train has a destination station $$$s_i$$$. When it enters $$$s_i$$$, it will stop there permanently. If at some point the train is going in the wrong direction, so that it will never be able to reach $$$s_i$$$ no matter where the switches point, it will immediately explode.

Find the latest possible time of the first explosion if you change switches optimally, or determine that you can direct every train to its destination so that no explosion occurs. Also, find the minimum number of times you need to change a switch to achieve this.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 10^5$$$) — the number of stations and trains, respectively.

The next $$$n-1$$$ lines describe the railroads. The $$$i$$$-th line contains three integers $$$u,v,d$$$ ($$$1\le u,v\le n$$$, $$$1\le d\le 10^9$$$), denoting a railroad from station $$$u$$$ to station $$$v$$$ with distance $$$d$$$. It is guaranteed that the railroads form a tree rooted at station $$$1$$$. The switch of a station $$$u$$$ is initially directed towards the last outgoing railroad from $$$u$$$ that appears in the input.

The next $$$m$$$ lines describe the trains. The $$$i$$$-th line contains two integers $$$s_i,t_i$$$ ($$$1\le s_i\le n$$$, $$$1\le t_1<t_2<\cdots<t_m\le 10^9$$$) — the destination station and the time the $$$i$$$-th train enters station $$$1$$$, respectively.

Output format:
Output two integers: the latest possible time of the first explosion (or $$$-1$$$ if it is possible to never have an explosion) and the minimum number of switch changes to achieve it.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
For the first test, here's an example timeline:

- At time $$$1$$$, train $$$1$$$ enters station $$$1$$$. We switch station $$$1$$$ to point to station $$$2$$$. Train $$$1$$$ is directed to station $$$2$$$.
- At time $$$2$$$, train $$$2$$$ enters station $$$1$$$, and train $$$1$$$ enters station $$$2$$$, where it stops permanently. We switch station $$$1$$$ to point to station $$$3$$$. Train $$$2$$$ is directed to station $$$3$$$.
- At time $$$4$$$, train $$$2$$$ enters station $$$3$$$. We switch station $$$3$$$ to point to station $$$4$$$. Train $$$2$$$ is directed to station $$$4$$$.
- At time $$$5$$$, train $$$2$$$ enters station $$$4$$$, where it stops permanently.
- At time $$$6$$$, train $$$3$$$ enters station $$$1$$$. We switch station $$$1$$$ to point to station $$$2$$$. Train $$$3$$$ is directed to station $$$2$$$.
- At time $$$7$$$, train $$$3$$$ enters station $$$2$$$, where it stops permanently. We switch station $$$3$$$ to point to station $$$5$$$.
- At time $$$10$$$, train $$$4$$$ enters station $$$1$$$. We switch station $$$1$$$ to point to station $$$3$$$. Train $$$4$$$ is directed to station $$$3$$$.
- At time $$$12$$$, train $$$4$$$ enters station $$$3$$$. Train $$$4$$$ is directed to station $$$5$$$.
- At time $$$15$$$, train $$$4$$$ enters station $$$5$$$, where it stops permanently.

For the second test, we switch nothing. At time $$$4$$$, train $$$2$$$ is directed to station $$$5$$$ and train $$$4$$$ is directed to station $$$3$$$. They both explode. It is impossible to prevent an explosion by time $$$4$$$.

For the third test, denote a switch change by $$$(u\to v,t)$$$ if we make station $$$u$$$ point to station $$$v$$$ at time $$$t$$$. One solution is to make these $$$4$$$ switch changes: $$$(1\to 2,1)$$$,$$$(1\to 3,2)$$$,$$$(7\to 8,5)$$$,$$$(5\to 6,8)$$$. At time $$$11$$$, trains $$$4$$$,$$$5$$$, and $$$6$$$ explode. It is impossible to prevent an explosion by time $$$11$$$.

Example input:
5 4
1 2 1
1 3 2
3 4 1
3 5 3
2 1
4 2
2 6
5 10

Example output:
-1 6

Example input:
5 4
1 2 1
1 3 2
3 4 1
3 5 3
5 1
4 2
4 3
2 4

Example output:
4 0

Editorial:
First, observe that a train can never pass one that enters earlier. So let's consider the trains independently. For a train $$$i$$$, look at the path from $$$1$$$ to $$$s_i$$$. We may need to change the switches of several stations on this path. We must make each switch within a time interval $$$(L, R]$$$, where $$$L$$$ is the most recent time some other train was directed the other way, and $$$R$$$ is the time train $$$i$$$ will enter the station. Let's mark all of these switches as changed before processing the next train.
Suppose the total number of switch changes is $$$k$$$, and for each station, we know its time intervals. We can manage all events in a priority queue of size $$$n$$$, always changing the switch with the earliest deadline that we can. Keep doing this until we are too late for a deadline, in which case an explosion happens, or until we have successfully made every switch change. This part will take $$$O(k\log n)$$$ time.
Let's find a nice upper bound on $$$k$$$. Note that the switches decompose the tree into a set of disjoint paths. When we process a train $$$i$$$, we are changing the switches to make a path from the root to $$$s_i$$$. It turns out this is exactly the same as an access operation on a link/cut tree! Because link/cut trees have $$$O(\log n)$$$ amortized time per operation, we can guarantee that the total number of switch changes is $$$k=O(n+m\log n)$$$.
Now let's consider the problem of finding all time intervals. We could use a link/cut tree, but everyone hates those, so let's discuss other methods. One strategy is to maintain a list of trains that go through a station, for every station. We start at the leaves and merge the lists going up. We can merge the lists efficiently by inserting elements from the smaller list to the larger list. Then a switch only needs to be changed when consecutive trains go to different children.
Unlike some of the testers, I wasn't smart enough to come up with the elegant small-to-large merging idea. So let's discuss an alternate solution using segment trees. When processing a train $$$i$$$, we want to do the following:
1. Find the top node $$$x$$$ of the path leading to $$$s_i$$$.
2. If $$$x$$$ is not the root, make the parent of $$$x$$$ point to $$$x$$$, and record the time interval we must make this switch. Repeat from step $$$1$$$ until $$$x$$$ is the root.
The queries we want to support are thus:
1. Find the time the most recent train passed through a node $$$x$$$ (ignoring trains with $$$s_i=x,$$$ where it only stops at $$$x$$$).
2. Find the top node of the path containing node $$$x$$$.
Let's handle queries of type $$$1$$$ with a segment tree. After processing train $$$i$$$, update the value at index $$$s_i$$$ to $$$i$$$. To answer a query, find the maximum value in the range corresponding to the relevant subtree.
Let's also handle queries of type $$$2$$$ with a segment tree. At a segment tree node, store the minimum value on its range. To answer a query, check the range $$$[x,x]$$$. Support lazy updates of the form "On a range $$$[l, r]$$$, replace all values $$$X$$$ with value $$$Y$$$, with the precondition that $$$X$$$ is currently the minimum value in $$$[l,r]$$$ and $$$Y$$$ will remain the minimum value after the update". To make a switch change, we only need to do two lazy updates.
Therefore, finding all the time intervals will take $$$O((m+k)\log n)$$$ time.
The overall complexity is $$$O(n\log n+m\log^2 n)$$$.