Description

题目译自 2023년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T3 「택시 여행」

IOI 国由 $N$ 个城市和连接这些城市的 $N-1$ 条双向道路组成，任意两个不同的城市都可以通过这些道路互相到达。也就是说，IOI 国的道路网络是一个树结构。

每个城市都有一个编号，从 $0$ 到 $N-1$，其中 $0$ 号城市是 IOI 国的首都。对于每个 $i$ $(0 \leq i \leq N-2)$，第 $i$ 条道路连接 $U[i]$ 号城市和 $V[i]$ 号城市，道路长度为 $W[i]$ 公里。

在 IOI 国，不同城市的出租车费用不同。具体来说，对于每个 $i$ $(0 \leq i \leq N-1)$，从 $i$ 号城市出发的出租车有一个基本费用 $A[i]$ 元和每公里的费用 $B[i]$ 元。这意味着，如果从 $i$ 号城市出发并行驶 $d$ 公里，需要支付 $A[i] + d \times B[i]$ 元。

小明目前住在首都 $0$ 号城市，他计划乘坐出租车去其他城市旅行。当他到达一个城市时，可以选择继续乘坐当前的出租车，或者换乘该城市出发的出租车。当然，换乘出租车需要支付基本费用，并且每公里的费用也可能不同。请计算从 0 号城市出发到达其他所有城市的最小费用。

你需要实现以下函数：

vector<long long> travel(vector<long long> A, vector<int> B, vector<int> U, vector<int> V, vector<int> W);

• 该函数只会被调用一次。
• A：大小为 $N$ 的整数数组。对于每个 $i$ $(0 \leq i \leq N-1)$，$A[i]$ 是从 $i$ 号城市出发的出租车的基本费用。
• B：大小为 $N$ 的整数数组。对于每个 $i$ $(0 \leq i \leq N-1)$，$B[i]$ 是从 $i$ 号城市出发的出租车的每公里费用。
• U, V, W：大小为 $N-1$ 的整数数组。对于每个 $i$ $(0 \leq i \leq N-2)$，$U[i]$ 号城市和 $V[i]$ 号城市之间有一条长度为 $W[i]$ 公里的道路。
• 该函数返回一个大小为 $N-1$ 的数组 $C$。对于每个 $i$ $(0 \leq i \leq N-2)$，$C[i]$ 是从 $0$ 号城市出发到达 $i+1$ 号城市的最小费用。

注意，提交的代码中不应包含任何输入输出操作。

Input Format

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$N$
• 第 $2$ 行：$A[0]\,A[1]\,\cdots\,A[N-1]$
• 第 $3$ 行：$B[0]\,B[1]\,\cdots\,B[N-1]$
• 第 $4+i$ $(0 \leq i \leq N-2)$ 行：$U[i]\,V[i]\,W[i]$

Output Format

示例评测程序按以下格式输出：

• 第 $i$ 行：函数 travel 返回的数组的第 $i$ 个元素

5
10 5 13 4 3
10 7 5 9 1
1 0 1
0 2 5
3 2 10
2 4 3

20
60
104
88

Hint

样例解释

考虑 $N=5, A=[10,5,13,4,3], B=[10,7,5,9,1], U=[1,0,3,2], V=[0,2,2,4], W=[1,5,10,3]$ 的情况。

评测程序将调用如下函数：

travel([10, 5, 13, 4, 3], [10, 7, 5, 9, 1], [1, 0, 3, 2], [0, 2, 2, 4], [1, 5, 10, 3]);

• 从 $0$ 号城市到 $1$ 号城市的最优方案是直接从 $0$ 号城市乘坐出租车，总费用为 $20$ 元。
• 从 $0$ 号城市到 $2$ 号城市的最优方案是直接从 $0$ 号城市乘坐出租车，总费用为 $60$ 元。
• 从 $0$ 号城市到 $4$ 号城市的最优方案是先从 $0$ 号城市乘坐出租车到 $1$ 号城市，然后换乘，再经过 $0$ 号和 $2$ 号城市到达 $4$ 号城市，总费用为 $88$ 元。
• 从 $0$ 号城市到 $3$ 号城市的最优方案是先从 $0$ 号城市乘坐出租车到 $1$ 号城市，然后换乘，再经过 $0$ 号和 $2$ 号城市到达 $4$ 号城市，再换乘，经过 $2$ 号城市到达 $3$ 号城市，总费用为 $104$ 元。

函数应返回 [20, 60, 104, 88]。

数据范围

对于所有输入数据，满足：

• $2 \leq N \leq 10^5$
• 对于所有 $i$ $(0 \leq i \leq N-1)$，$0 \leq A[i] \leq 10^{12}$
• 对于所有 $i$ $(0 \leq i \leq N-1)$，$0 \leq B[i] \leq 10^6$
• 对于所有 $i$ $(0 \leq i \leq N-2)$，$0 \leq U[i], V[i] \leq N-1 ; U[i] \neq V[i]$
• 对于所有 $i$ $(0 \leq i \leq N-2)$，$1 \leq W[i] \leq 10^6$

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