Paths on the Tree

题意翻译

给定一个 $n$ 个节点的树，其节点被标记为 $1$ 到 $n$，而且该树的根为 $1$，另外也给定一个积分序列 $s$。 如果下列两个条件都满足，则我们称路径集合k可用： - 该集合内所有路径从 $1$ 开始 - $c_i$ 为覆盖节点 $i$ 的路径数量，对于每对拥有同个父节点的节点 $(u,v)$，要求$|c_u-c_v|$ 小于等于1 对于每个路径集合，其权值被定义为 $ \sum\limits_{i=1}^n c_i s_i $ 。 显而易见，每组数据至少有一个可用的路径集合，找出所有可用路径集合中的最大权值。 输入 第一行为数据组数 $t$。 接下来对于每组数据： 第一行输入树的大小 $n$ 和需求的路径数量 $k$。 第二行输入一个数组 $p$，长度为 $n-1$，其中 $p_i$ 为 $i+1$ 节点的父节点。 第三行输入一个数组 $s$，长度为 $n$，即为题面中所指的积分序列。 输出 对于每组数据，输出路径集合中的最大值。 样例解释 对于第一组数据，最优解为下列四条路径所构成的集合 $ 1 \to 2 \to 3 \to 5 $ , $ 1 \to 2 \to 3 \to 5 $ , $ 1 \to 4 $ , $ 1 \to 4 $，$c$ 数组为 ${4,2,2,2,2}$，可得其权值为 $ 4\cdot 6+ 2\cdot 2+2\cdot 1+2\cdot 5+2\cdot 7=54 $。 对于第二组数据，最优解为下列三条路径所构成的集合$ 1 \to 2 \to 3 \to 5 $ , $ 1 \to 2 \to 3 \to 5 $ , $ 1 \to 4 $，$c$ 数组为 $3,2,2,1,2$，可得其权值为 $ 3\cdot 6+ 2\cdot 6+2\cdot 1+1\cdot 4+2\cdot 10=56 $。 说明 对于 $100\%$ 的数据，$ 1 \leq t \leq 10^4 $，$ 2 \le n \le 2 \cdot 10^5 $，$ 1 \le k \le 10^9 $，$ 1\le p_i\le n $，$ 0 \le s_i \le 10^4 $。 对于单组测试数据，$n$ 的总和不超过 $2\cdot10^5$。 翻译 @[zymooll](/user/289296)

题目描述

You are given a rooted tree consisting of $ n $ vertices. The vertices are numbered from $ 1 $ to $ n $ , and the root is the vertex $ 1 $ . You are also given a score array $ s_1, s_2, \ldots, s_n $ . A multiset of $ k $ simple paths is called valid if the following two conditions are both true. - Each path starts from $ 1 $ . - Let $ c_i $ be the number of paths covering vertex $ i $ . For each pair of vertices $ (u,v) $ ( $ 2\le u,v\le n $ ) that have the same parent, $ |c_u-c_v|\le 1 $ holds. The value of the path multiset is defined as $ \sum\limits_{i=1}^n c_i s_i $ .It can be shown that it is always possible to find at least one valid multiset. Find the maximum value among all valid multisets.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains two space-separated integers $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) and $ k $ ( $ 1 \le k \le 10^9 $ ) — the size of the tree and the required number of paths. The second line contains $ n - 1 $ space-separated integers $ p_2,p_3,\ldots,p_n $ ( $ 1\le p_i\le n $ ), where $ p_i $ is the parent of the $ i $ -th vertex. It is guaranteed that this value describe a valid tree with root $ 1 $ . The third line contains $ n $ space-separated integers $ s_1,s_2,\ldots,s_n $ ( $ 0 \le s_i \le 10^4 $ ) — the scores of the vertices. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10 ^ 5 $ .

输出格式

For each test case, print a single integer — the maximum value of a path multiset.

输入输出样例

输入样例 #1

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

输出样例 #1

54
56

说明

In the first test case, one of optimal solutions is four paths $ 1 \to 2 \to 3 \to 5 $ , $ 1 \to 2 \to 3 \to 5 $ , $ 1 \to 4 $ , $ 1 \to 4 $ , here $ c=[4,2,2,2,2] $ . The value equals to $ 4\cdot 6+ 2\cdot 2+2\cdot 1+2\cdot 5+2\cdot 7=54 $ . In the second test case, one of optimal solution is three paths $ 1 \to 2 \to 3 \to 5 $ , $ 1 \to 2 \to 3 \to 5 $ , $ 1 \to 4 $ , here $ c=[3,2,2,1,2] $ . The value equals to $ 3\cdot 6+ 2\cdot 6+2\cdot 1+1\cdot 4+2\cdot 10=56 $ .

**题目大意：**

给定一个有 $ n $ 个节点的树，节点编号为 $ 1 $ 到 $ n $，根节点为 $ 1 $，同时给定一个积分序列 $ s $。需要找到一系列从 $ 1 $ 开始的路径，使得：

- 对于每对具有相同父节点的节点 $ (u,v) $，路径覆盖节点 $ u $ 和 $ v $ 的数量之差的绝对值不超过 $ 1 $。
- 每组数据的路径总数为 $ k $。

路径集合的权值定义为所有节点被覆盖次数与对应积分的乘积之和。对于每组数据，至少存在一个有效的路径集合，需要找出所有有效路径集合中的最大权值。

**输入输出数据格式：**

**输入格式：**

- 第一行包含一个整数 $ t $，表示数据组数。
- 每组数据包含三行：
- 第一行包含两个整数 $ n $ 和 $ k $，分别表示树的大小和需求的路径数量。
- 第二行包含 $ n-1 $ 个整数，表示每个节点的父节点。
- 第三行包含 $ n $ 个整数，表示积分序列。

**输出格式：**

- 对于每组数据，输出一个整数，表示路径集合中的最大权值。

**样例解释：**

- 第一组数据的最优解是四条路径：$ 1 \to 2 \to 3 \to 5 $，$ 1 \to 2 \to 3 \to 5 $，$ 1 \to 4 $，$ 1 \to 4 $。其权值为 $ 4 \times 6 + 2 \times 2 + 2 \times 1 + 2 \times 5 + 2 \times 7 = 54 $。
- 第二组数据的最优解是三条路径：$ 1 \to 2 \to 3 \to 5 $，$ 1 \to 2 \to 3 \to 5 $，$ 1 \to 4 $。其权值为 $ 3 \times 6 + 2 \times 6 + 2 \times 1 + 1 \times 4 + 2 \times 10 = 56 $。

**说明：**

- 对于 $ 100\% $ 的数据，$ 1 \leq t \leq 10^4 $，$ 2 \le n \le 2 \times 10^5 $，$ 1 \le k \le 10^9 $，$ 1 \le p_i \le n $，$ 0 \le s_i \le 10^4 $。
- 对于单组测试数据，$ n $ 的总和不超过 $ 2 \times 10^5 $。**题目大意：** 给定一个有 $ n $ 个节点的树，节点编号为 $ 1 $ 到 $ n $，根节点为 $ 1 $，同时给定一个积分序列 $ s $。需要找到一系列从 $ 1 $ 开始的路径，使得： - 对于每对具有相同父节点的节点 $ (u,v) $，路径覆盖节点 $ u $ 和 $ v $ 的数量之差的绝对值不超过 $ 1 $。 - 每组数据的路径总数为 $ k $。 路径集合的权值定义为所有节点被覆盖次数与对应积分的乘积之和。对于每组数据，至少存在一个有效的路径集合，需要找出所有有效路径集合中的最大权值。 **输入输出数据格式：** **输入格式：** - 第一行包含一个整数 $ t $，表示数据组数。 - 每组数据包含三行： - 第一行包含两个整数 $ n $ 和 $ k $，分别表示树的大小和需求的路径数量。 - 第二行包含 $ n-1 $ 个整数，表示每个节点的父节点。 - 第三行包含 $ n $ 个整数，表示积分序列。 **输出格式：** - 对于每组数据，输出一个整数，表示路径集合中的最大权值。 **样例解释：** - 第一组数据的最优解是四条路径：$ 1 \to 2 \to 3 \to 5 $，$ 1 \to 2 \to 3 \to 5 $，$ 1 \to 4 $，$ 1 \to 4 $。其权值为 $ 4 \times 6 + 2 \times 2 + 2 \times 1 + 2 \times 5 + 2 \times 7 = 54 $。 - 第二组数据的最优解是三条路径：$ 1 \to 2 \to 3 \to 5 $，$ 1 \to 2 \to 3 \to 5 $，$ 1 \to 4 $。其权值为 $ 3 \times 6 + 2 \times 6 + 2 \times 1 + 1 \times 4 + 2 \times 10 = 56 $。 **说明：** - 对于 $ 100\% $ 的数据，$ 1 \leq t \leq 10^4 $，$ 2 \le n \le 2 \times 10^5 $，$ 1 \le k \le 10^9 $，$ 1 \le p_i \le n $，$ 0 \le s_i \le 10^4 $。 - 对于单组测试数据，$ n $ 的总和不超过 $ 2 \times 10^5 $。