← 返回题目列表

Codeforces · 1344/E

E. 火车轨道

中文机器翻译题面 查看原题

没错。我是普渡大学的学生,我厚颜无耻地写了一道关于火车的问题。

有$$$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$$$,它就会立即爆炸。

如果您以最佳方式更改开关,则找到第一次爆炸的最晚可能时间,或者确定您可以将每列火车引导至目的地,以便不发生爆炸。另外,请找出实现此目的所需更改开关的最少次数。

输入

第一行包含两个整数 $$$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<t_2<\cdots<t_m\le 10^9$$$) - 分别是目的地车站和第 $$$i$$$ 列车进入车站 $$$1$$$ 的时间。

输出

输出两个整数:第一次爆炸的最晚可能时间(或者 $$$-1$$$ 如果可能永远不会发生爆炸)以及实现它的最小开关更改次数。

示例

输入 #1

5 4
1 2 1
1 3 2
3 4 1
3 5 3
2 1
4 2
2 6
5 10

输出 #1

-1 6

输入 #2

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

输出 #2

4 0

输入 #3

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

输出 #3

11 4

注意

对于第一个测试,下面是一个示例时间线:

- 在时间 $$$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$$$ 在时间 $$$t$$$ 指向站 $$$v$$$,则用 $$$(u\to v,t)$$$ 表示开关更改。一种解决方案是进行以下 $$$4$$$ 开关更改:$$$(1\to 2,1)$$$、$$$(1\to 3,2)$$$、$$$(7\to 8,5)$$$、$$$(5\to 6,8)$$$。在 $$$11$$$ 时刻,火车 $$$4$$$、$$$5$$$ 和 $$$6$$$ 爆炸。在$$$11$$$时间之前阻止爆炸是不可能的。