← 返回题目列表

Codeforces · 1583/H

H. 奥姆卡和旅游

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

Omkar 正在举办他的国家 Omkarland 之旅!奥姆卡兰有 $$$n$$$ 个城市,而且奇怪的是,恰好有 $$$n-1$$$ 双向道路将城市相互连接。保证您可以从任何一个城市通过路网到达任何一个城市。

每个城市都有其享受价值$$$e$$$。每条道路都有容量 $$$c$$$,表示其上可行驶的最大车辆数量,以及相关的通行费 $$$t$$$。然而,翁卡兰的收费系统有一个有趣的怪癖:如果车辆在一次旅程中在多条道路上行驶,他们只需支付所行驶的任何一条道路中最高的通行费。 (换句话说,他们在行驶的所有道路上支付 $$$\max t$$$ 费用。)如果车辆不经过任何道路,他们将支付 $$$0$$$ 通行费。

Omkar 决定举办 $$$q$$$ 旅游团。每个旅行团由 $$$v$$$ 车辆组成,从城市 $$$x$$$ 出发。 (请记住,拥有 $$$v$$$ 车辆的旅游团只能在容量为 $$$\geq v$$$ 的道路上行驶。)作为旅游组织者,Omkar 希望他的团队尽可能享受乐趣,但也必须偿还团队必须支付的通行费。因此,对于每个旅行团,Omkar 想知道两件事:第一,该旅行团从出发城市可以到达的最大享受值是多少,该城市的享受价值 $$$y$$$ 是多少;第二,Omkar 需要为整个旅行团从 $$$x$$$ 到 $$$y$$$ 的旅程支付每辆车多少钱? (从 $$$x$$$ 到 $$$y$$$ 的行程始终位于从 $$$x$$$ 到 $$$y$$$ 的最短路径上。)

在有多个可到达城市且享受价值最大的情况下,Omkar会让他的旅行团选择他们想去哪一个。因此,为了应对所有可能的情况,他想知道每辆车需要多少钱,以保证无论他们选择哪个城市,他都可以报销团队。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$),分别代表城市数量和组数量。

下一行包含 $$$n$$$ 整数 $$$e_1, e_2, \ldots, e_n$$$ ($$$1 \leq e_i \leq 10^9$$$),其中 $$$e_i$$$ 代表城市 $$$i$$$ 的享受值。

接下来的 $$$n-1$$$ 行每行包含四个整数 $$$a$$$、$$$b$$$、$$$c$$$ 和 $$$t$$$ ($$$1 \leq a,b \leq n$$$, $$$1 \leq c \leq 10^9$$$, $$$1 \leq t \leq 10^9$$$),代表城市 $$$a$$$ 和城市 $$$b$$$ 之间的道路,通行能力为 $$$c$$$,收费为 $$$t$$$。

接下来的$$$q$$$行每行包含两个整数$$$v$$$和$$$x$$$($$$1 \leq v \leq 10^9$$$, $$$1 \leq x \leq n$$$),分别代表旅行团和出发城市的车辆数量。

输出

输出 $$$q$$$ 行。第$$$i$$$行应包含两个整数:第$$$i$$$个旅行团所能到达的城市的最高享受价值,以及Omkar需要保证能够报销第$$$i$$$个旅行团的每辆车的金额。

示例

输入 #1

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

输出 #1

3 8
3 0
3 2

输入 #2

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

输出 #2

1 0
2 1
3 1
4 1
5 1

输入 #3

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

输出 #3

2 8
2 8
2 3
2 1
1 0

注意

第一个样本的地图如下所示。对于节点,非粗体数字表示索引,粗体数字表示享受值。对于边缘,非粗体数字代表容量,粗体数字代表通行费。

对于第一个查询,从城市$$$3$$$出发的规模为$$$1$$$的旅行团可以到达城市$$$1$$$、$$$2$$$、$$$3$$$、$$$4$$$和$$$5$$$。因此,他们能达到的最大享受价值是$$$3$$$。如果旅行团选择去市区$$$4$$$,Omkar每辆车需支付$$$8$$$,这是最高限额。

对于第二个查询,从城市$$$5$$$出发的规模为$$$9$$$的旅行团只能到达城市$$$5$$$。因此,最大可达到的享受价值仍然是$$$3$$$,Omkar将为每辆车支付$$$0$$$。

对于第三个查询,从城市$$$2$$$出发的规模为$$$6$$$的旅行团可以到达城市$$$2$$$和$$$4$$$。最大可达到的享受价值还是$$$3$$$。如果旅行团选择去市区$$$4$$$,Omkar每辆车需支付$$$2$$$,这是最高限额。

第二个样本的地图如下所示:

对于第一个查询,从城市$$$1$$$出发的规模为$$$5$$$的旅行团只能到达城市$$$1$$$。因此,他们的最大享受价值为 $$$1$$$,而 Omkar 必须支付的成本为每辆车 $$$0$$$。

对于第二个查询,从城市$$$1$$$出发的规模为$$$4$$$的旅行团可以到达城市$$$1$$$和$$$2$$$。因此,他们的最大享受价值为 $$$2$$$,Omkar 将为每辆车支付 $$$1$$$。

对于第三个查询,从城市$$$1$$$出发的规模为$$$3$$$的旅行团可以到达城市$$$1$$$、$$$2$$$和$$$3$$$。因此,他们的最大享受价值为 $$$3$$$,Omkar 将为每辆车支付 $$$1$$$。

对于第四个查询,从城市$$$1$$$出发的规模为$$$2$$$的旅行团可以到达城市$$$1$$$、$$$2$$$、$$$3$$$和$$$4$$$。因此,他们的最大享受价值为 $$$4$$$,Omkar 将为每辆车支付 $$$1$$$。

对于第五个查询,从城市$$$1$$$出发的规模为$$$1$$$的旅行团可以到达城市$$$1$$$、$$$2$$$、$$$3$$$、$$$4$$$和$$$5$$$。因此,他们的最大享受价值为 $$$5$$$,Omkar 将为每辆车支付 $$$1$$$。