CF1746D.Paths on the Tree

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.

你被给定一棵包含 $n$ 个顶点的有根树。顶点编号为 $1$ 到 $n$，根节点为顶点 $1$。同时，你还被给定一个分数数组 $s_1, s_2, \ldots, s_n$。

一个包含 $k$ 条简单路径的多重集被称为合法的，当且仅当以下两个条件均成立：

• 每条路径均从顶点 $1$ 出发；
• 设 $c_i$ 表示覆盖顶点 $i$ 的路径条数。对任意一对具有相同父节点的顶点 $(u,v)$（其中 $2\le u,v\le n$），均有 $|c_u-c_v|\le 1$。

该路径多重集的值定义为 $\sum\limits_{i=1}^n c_i s_i$。

可以证明，总存在至少一个合法的多重集。请找出所有合法多重集中最大的值。

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

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个以空格分隔的整数 $n$（$2 \le n \le 2 \cdot 10^5$）和 $k$（$1 \le k \le 10^9$），分别表示树的大小以及所需路径的数量。

第二行包含 $n - 1$ 个以空格分隔的整数 $p_2,p_3,\ldots,p_n$（$1\le p_i\le n$），其中 $p_i$ 表示第 $i$ 个顶点的父节点。保证这些值构成一棵以 $1$ 为根的合法树。

第三行包含 $n$ 个以空格分隔的整数 $s_1,s_2,\ldots,s_n$（$0 \le s_i \le 10^4$），表示各顶点的分数。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10 ^ 5$。

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

对于每个测试用例，输出一个整数——路径多重集的最大值。

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

在第一个测试用例中，一种最优解包含四条路径：$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$。