AdditionalFile4971.zip

P3591 [POI 2015 R3] 访问 Visits

题目描述

给定一棵 $n$ 个点的树，树上每条边的长度都为 $1$，第 $i$ 个点的权值为 $a_i$。

Byteasar 想要走遍这整棵树，他会按照某个 $1$ 到 $n$ 的全排列 $b$ 走 $n-1$ 次，第 $i$ 次他会从 $b_i$ 点走到 $b_{i + 1}$ 点，并且这一次的步伐大小为 $c_i$。

对于一次行走，假设起点为 $x$，终点为 $y$，步伐为 $k$，那么 Byteasar 会从 $x$ 开始，每步往前走 $k$ 条边，数据保证了每次行走的距离是 $k$ 的倍数。

请帮助 Byteasar 统计出每一次行走时经过的所有点的权值和。

输入格式

第一行包含一个正整数 $n$（$2 \le n \le 50000$）。表示节点的个数。

第二行包含 $n$ 个正整数，其中第 $i$ 个数为 $a_i$（$1 \le a_i \le 10000$），分别表示每个点的权值。

接下来 $n-1$ 行，每行包含两个正整数 $u,v$（$1 \le u,v \le n$），表示 $u$ 与 $v$ 之间有一条边。

接下来一行包含 $n$ 个互不相同的正整数，其中第 $i$ 个数为 $b_i$（$1 \le b_i \le n$），表示行走路线。

接下来一行包含 $n-1$ 个正整数，其中第 $i$ 个数为 $c_i$（$1 \le c_i < n$），表示每次行走的步伐大小。

输出格式

包含 $n-1$ 行，每行一个正整数，依次输出每次行走时经过的所有点的权值和。

输入输出样例 #1

输入 #1

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

输出 #1

10
6
10
5

说明/提示

原题名称：Odwiedziny。

#4971. 「POI2015 R3」访问 Visits

标签: 传统 | 时间限制: 2500 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXII Olimpiada Informatyczna — III etap Odwiedziny

Bajtazar 是个不平凡的人——过去 $21$ 年，他当过邮差、银行家、滑冰选手，甚至国王！难怪他朋友遍天下。可惜，频繁跳槽让他与许多老友渐行渐远。现在，他决定在字节城展开一场盛大的巡游，重拾旧日友情！

字节城有 $n$ 座城市，通过 $n-1$ 条双向道路相连。Bajtazar 已定好访问每座城市的顺序，计划在 BMW 租车，沿最短路径在相邻访问城市间穿梭。租车免费，但需加油——容量为 $k$ 的车在起点城市和每行驶 $k$ 条道路后需加油。BMW 了解 Bajtazar 的行程，特意为每段路程挑选了油箱容量，确保他在终点城市也需加油，以最快完成旅程。

已知 Bajtazar 的访问顺序、各城市加油价格和租车油箱容量，请你计算他每段路程的加油总成本。

输入格式

第一行包含一个整数 $n$ $(2 \leq n \leq 50000)$，表示字节城城市数量。城市编号为 $1$ 到 $n$。

第二行包含 $n$ 个整数 $c_1, \ldots, c_n$ $(1 \leq c_i \leq 10000)$，$c_i$ 表示 $i$ 号城市加油站的油箱填充成本。

接下来的 $n-1$ 行描述道路，每行包含两个整数 $a, b$ $(1 \leq a, b \leq n)$，表示 $a$ 号和 $b$ 号城市间有双向道路。

下一行包含 $n$ 个整数 $t_1, \ldots, t_n$，表示 Bajtazar 访问城市的顺序（$1$ 到 $n$ 各出现一次）。

最后一行包含 $n-1$ 个整数 $k_1, \ldots, k_{n-1}$，$k_i$ 表示从 $t_i$ 号城市到 $t_{i+1}$ 号城市使用的车的油箱容量，需每 $k_i$ 条道路加油一次。保证 $k_i$ 整除两城市间的道路数。

输出格式

输出 $n-1$ 行，每行一个整数，第 $i$ 行表示从 $t_i$ 号城市到 $t_{i+1}$ 号城市的加油总成本。

样例

输入

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

输出

10
6
10
5

数据范围与提示

对于 $28\%$ 的数据，$n \leq 1000$。
对于 $36\%$ 的数据，$n \leq 10000$。