AdditionalFile5002.zip

#5002. 「POI 2023/2024 R3」Wyjścia ewakuacyjne

标签: 传统 | 时间限制: 8000 ms | 内存限制: 512 MiB |

题目描述

题目译自 XXXI Olimpiada Informatyczna – III etap Wyjścia ewakuacyjne

BajtoCorp 公司正搬入新建大楼。大楼包含 $n$ 个房间（编号 $1$ 至 $n$）和 $n-1$ 个连接房间的走廊（编号 $1$ 至 $n-1$）。任意两房间间有唯一路径（不回头）。第 $i$ 个房间初始有 $a_i$ 人，第 $j$ 个走廊最大通行 $b_j$ 人。

部分房间需设置紧急出口，其余房间各需放置一个绿色箭头，指向相邻房间，指引疏散路径。箭头需确保沿其方向可达某出口。疏散时，房间内初始人员或进入人员均沿箭头方向移动。需规划路径，使第 $j$ 个走廊的总通行人数不超过 $b_j$（考虑最坏情况）。房间通行人数无限制。

你的任务是计算所需紧急出口的最小数量。

输入格式

第一行包含一个整数 $n$ $(2 \leq n \leq 1000000)$，表示房间数。

第二行包含 $n$ 个整数 $a_i$ $(1 \leq a_i \leq 10^{12})$，表示第 $i$ 个房间的初始人数。

接下来的 $n-1$ 行，每行包含三个整数 $x_j, y_j, b_j$ $(1 \leq x_j < y_j \leq n, 1 \leq b_j \leq 10^{18})$，表示第 $j$ 个走廊连接房间 $x_j$ 和 $y_j$，最大通行 $b_j$ 人。

输出格式

输出一个整数，表示大楼所需紧急出口的最小数量。

样例

输入

10
20 30 64 10 4 80 20 5 10 4
1 2 80
2 3 90
3 4 60
4 5 4
5 6 4
2 7 80
3 8 10
4 9 20
5 10 4

输出

3

房间 $6$ 必须设出口，因其 $80$ 人无法通过容量仅 $4$ 的走廊。另一出口可设于房间 $2$ 或 $3$，服务房间 $1, 2, 3, 4, 7, 8, 9$。注意，房间 $10$ 的 $4$ 人须与房间 $5$ 的 $4$ 人同向疏散，此 $8$ 人无法通过走廊至房间 $4$ 或 $6$，故需在房间 $5$ 或 $10$ 再设一出口，总计 $3$ 个。

附加样例

1. $n=10, a_i=i \cdot 10^{10}, b_j=(10-j) \cdot 10^{10}$，满足子任务 $1$。
2. $n=1023$，大楼为以 $1$ 为根的满二叉树（$x_j=\lceil j/2 \rceil, y_j=j+1$），满足子任务 $2$。
3. $n=1000000$，大楼为以 $1$ 为根的三叉树（$x_j=\lceil j/3 \rceil, y_j=j+1$），$a_i=(i \bmod 17)+1, b_j=(j \bmod 23)+1$。

数据范围与提示

详细子任务附加限制及分值如下表所示。