Paths on the Tree

给定一个 $n$ 个节点的树，其节点被标记为 $1$ 到 $n$，而且该树的根为 $1$，另外也给定一个权值序列 $s$。 如果下列两个条件都满足，则我们称含有 $k$ 条路径的路径集合 $\mathscr P$ 合法： - $\mathscr P$ 内所有路径从 $1$ 出发； - $c_i$ 为覆盖节点 $i$ 的路径数量，对于每对拥有同个父节点的节点 $(u,v)$，要求$|c_u-c_v|$ 小于等于 $1$。 对于 $\mathscr P$，其权值被定义为： $$ \mathrm{value}({\mathscr P})=\sum\limits_{i=1}^n c_i s_i $$ 显而易见，每组数据至少有一个可用的路径集合，找出所有合法的 ${\mathscr P}$ 的最大权值。 ### 输入 第一行为数据组数 $T$。 接下来对于每组数据： 第一行输入树的大小 $n$ 和需求的路径数量 $k$。 第二行输入一个数组 $p$，长度为 $n-1$，其中 $p_i$ 为 $i+1$ 节点的父节点。 第三行输入一个数组 $s$，长度为 $n$，即为题面中所指的权值序列。 ### 输出 对于每组数据，输出最大的 $\mathrm{value}({\mathscr P})$。 ### 样例解释 对于第一组数据，最优解为下列四条路径所构成的集合 $ 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.

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

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 $ .