CF1344E.Train Tracks

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.

没错，我是普渡大学的学生，而且我毫不羞耻地出了一道关于火车的题目。

共有 $n$ 个车站和 $m$ 列火车。这些车站由 $n-1$ 条单向铁路连接，构成一棵以车站 $1$ 为根的树。所有铁路的方向均从根节点（车站 $1$）指向叶子节点。一条铁路连接车站 $u$ 与车站 $v$，其距离为 $d$，即从 $u$ 行驶到 $v$ 需耗时 $d$。

每个至少拥有一条出向铁路的车站都装有一个道岔开关，用于决定驶入该车站的火车将被导向哪一个子车站。例如，其结构可能如下图所示：

此处，车站 $1$ 和 $3$ 的道岔分别指向车站 $2$ 和 $4$。

初始时刻，没有任何火车位于任何车站。第 $i$ 列火车将在时刻 $t_i$ 进入车站 $1$。从时刻 $1$ 开始，每一单位时间依次执行以下两个步骤：

1. 你最多可将一个车站的道岔切换至指向另一个子车站（若存在多个子车站）。道岔切换在步骤 $2$ 执行前即时生效。
2. 对于每一个当前位于车站 $u$ 的火车，它将依据 $u$ 处道岔所指示的方向，驶向车站 $v$。即：若 $u$ 到 $v$ 的铁路距离为 $d$，则该火车将在 $d$ 单位时间后进入车站 $v$。

每列火车均有其目标车站 $s_i$。当它进入 $s_i$ 后，将永久停驻于此。若在某一时刻，某列火车正驶向错误方向（即无论后续如何调整道岔，该火车均无法再抵达 $s_i$），则它将立即爆炸。

请在最优调整道岔的前提下，求出首次爆炸发生的最晚可能时刻；若可保证所有火车均能抵达各自目的地而无任何爆炸发生，则说明这种情况可行，并进一步求出达成此目标所需的最少道岔切换次数。

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 \lt t_2 \lt \cdots \lt t_m\le 10^9$) — the destination station and the time the $i$-th train enters station $1$, respectively.

第一行包含两个整数 $n$ 和 $m$（$1\le n,m\le 10^5$），分别表示车站数量和列车数量。

接下来的 $n-1$ 行描述铁路线。第 $i$ 行包含三个整数 $u,v,d$（$1\le u,v\le n$, $1\le d\le 10^9$），表示一条从车站 $u$ 到车站 $v$、长度为 $d$ 的铁路线。保证这些铁路线构成一棵以车站 $1$ 为根的树。每个车站 $u$ 的道岔初始时指向输入中最后出现的、从 $u$ 出发的那条铁路线。

接下来的 $m$ 行描述列车。第 $i$ 行包含两个整数 $s_i,t_i$（$1\le s_i\le n$, $1\le t_1 \lt t_2 \lt \cdots \lt t_m\le 10^9$），分别表示第 $i$ 辆列车的目的地车站，以及该列车进入车站 $1$ 的时刻。

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.

输出两个整数：首次爆炸最晚可能发生的时间（若可避免任何爆炸，则输出 $-1$），以及达成该时间所需的最小开关切换次数。

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$.

对于第一个测试，以下是一个时间线示例：

• 在时刻 $1$，列车 $1$ 进入车站 $1$。我们将车站 $1$ 的开关切换为指向车站 $2$，从而将列车 $1$ 引导至车站 $2$。
• 在时刻 $2$，列车 $2$ 进入车站 $1$，同时列车 $1$ 进入车站 $2$ 并永久停靠于此。我们将车站 $1$ 的开关切换为指向车站 $3$，从而将列车 $2$ 引导至车站 $3$。
• 在时刻 $4$，列车 $2$ 进入车站 $3$。我们将车站 $3$ 的开关切换为指向车站 $4$，从而将列车 $2$ 引导至车站 $4$。
• 在时刻 $5$，列车 $2$ 进入车站 $4$ 并永久停靠于此。
• 在时刻 $6$，列车 $3$ 进入车站 $1$。我们将车站 $1$ 的开关切换为指向车站 $2$，从而将列车 $3$ 引导至车站 $2$。
• 在时刻 $7$，列车 $3$ 进入车站 $2$ 并永久停靠于此。我们将车站 $3$ 的开关切换为指向车站 $5$。
• 在时刻 $10$，列车 $4$ 进入车站 $1$。我们将车站 $1$ 的开关切换为指向车站 $3$，从而将列车 $4$ 引导至车站 $3$。
• 在时刻 $12$，列车 $4$ 进入车站 $3$。列车 $4$ 被引导至车站 $5$。
• 在时刻 $15$，列车 $4$ 进入车站 $5$ 并永久停靠于此。

对于第二个测试，我们不进行任何开关切换。在时刻 $4$，列车 $2$ 被引导至车站 $5$，而列车 $4$ 被引导至车站 $3$，二者均发生爆炸。因此，无法在时刻 $4$ 之前避免爆炸。

对于第三个测试，用 $(u\to v,t)$ 表示在时刻 $t$ 将车站 $u$ 的开关切换为指向车站 $v$。一种可行方案是执行以下 $4$ 次开关切换：$(1\to 2,1)$、$(1\to 3,2)$、$(7\to 8,5)$、$(5\to 6,8)$。在时刻 $11$，列车 $4$、$5$ 和 $6$ 发生爆炸。因此，无法在时刻 $11$ 之前避免爆炸。