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$。 如果下列两个条件都满足，则我们称路径集合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)