P10065 [SNOI2024] 字符树

给你一个 $n$ 个点的有根树，根为 $1$。每条边上有一个字符 $c = \{0, 1\}$。$S_u$ 表示从根到 $u$ 的路径上每条边的字符依次写下来组成的字符串。保证每个节点向儿子的边上的字符互不相同。 对每个点 $u$，有一个价值 $\mathit{val}_u$ 和一个限制 $a_u$。对每个点 $u$，如果点 $v$ 满足 $S_u$ 是 $S_v$ 的后缀。那么我们认为 $v$ 是的 $u$ 扩展点。 Alice 手里有一个字符串 $S$，初始令 $S = S_u$，现在他可以删掉若干末尾的字符，使得 $S$ 变成 $S'$。并将 $S'$ 告诉给 Bob。 Bob 获得了一个字符串 $S'$，他需要在 $S'$ 之后加入若干字符，并获得 $S''$。对于某个 $u$ 的扩展点 $v$，满足 $S'' = S_v$，并且 $\lvert S' \rvert \ge a_v$，那么 Bob 就获得了 $\mathit{val}_v$ 的收益，当然 Bob 只能进行一次这样的操作，所以他会选择符合条件的 $v$ 里，$\mathit{val}_v$ 最大的那个。如果没有符合条件的 $v$，Bob 只能获得 $0$ 的收益。 现在 Alice 想知道，对于删除 $0 \sim \lvert S \rvert$ 个字符，总计 $\lvert S \rvert + 1$ 种删除方式里 Bob 能获得权值之和是多少？ 对于每个 $u$，你都需要回答 Alice 的询问。 形式化地说： 我们需要对每个点 $u$ 求出 $\mathit{ans}_u = \sum\limits_{0 \le i \le \lvert S_u \rvert} \max\limits_{i \ge a_v \land S_u = S_v[\lvert S_v \rvert - \lvert S_u \rvert + 1, \lvert S_v \rvert] \land S_u[1, i] = S_v[1, i]} \mathit{val}_v$。 特殊的，如果对于某个 $u$，不存在任何 $v$ 满足条件，那么 $\max = 0$。 其中 $S[l, r]$ 表示字符串 $S$ 的第 $l$ 到第 $r$ 个字符组成的字符串。特殊的，$S[x + 1, x]$ 表示空串。$\lvert S \rvert$ 表示字符串 $S$ 的长度，$\land$ 表示且。

多组测试数据，第一行一个整数 $T$ 表示数据组数。 对于每组测试数据，第一行一个正整数 $n$，表示节点个数。 接下来 $n - 1$ 行，每行两个整数 $\mathit{fa}_i, c_i$ 表示第 $i$ 个点的父亲编号，以及边上的字符。 接下来一行 $n$ 个正整数 $\mathit{val}_1, \mathit{val}_2, \ldots, \mathit{val}_n$。 接下来一行 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$。

输出一行 $n$ 个整数 $\mathit{ans}_1, \mathit{ans}_2, \ldots, \mathit{ans}_n$。

**【样例 \#1 解释】** 以下表格表示当 $u, i$ 固定时，式子中 $\mathit{val}_v$ 的最大值。 | | $u = 1$ | $u = 2$ | $u = 3$ | $u = 4$ | $u = 5$ | |:-:|:-:|:-:|:-:|:-:|:-:| | $i = 0$ | $3$ | $0$ | $3$ | $0$ | $0$ | | $i = 1$ | - | $4$ | $3$ | $4$ | $0$ | | $i = 2$ | - | - | - | $4$ | $5$ | --- **【样例 \#2】** 见附件中 `tree/tree2.in` 与 `tree/tree2.ans`。 这个样例满足测试点 $3 \sim 5$ 的条件限制。 --- **【样例 \#3】** 见附件中 `tree/tree3.in` 与 `tree/tree3.ans`。 这个样例满足测试点 $9 \sim 10$ 的条件限制。 --- **【样例 \#4】** 见附件中 `tree/tree4.in` 与 `tree/tree4.ans`。 这个样例满足测试点 $11 \sim 12$ 的条件限制。 --- **【数据范围】** 对于所有数据保证 $1 \le T \le 5$，$1 \le n \le 5 \times {10}^5$，$1 \le \mathit{val}_i \le {10}^9$，$1 \le \mathit{fa}_i < i$，$c_i = \{0, 1\}$，$0 \le a_i \le n$。 具体如下： | 测试点编号 | $n \le$ | 特殊性质 | |:-:|:-:|:-:| | $1 \sim 2$ | $100$ | 无 | | $3 \sim 5$ | $2 \times {10}^3$ | 无 | | $6 \sim 8$ | ${10}^4$ | 无 | | $9 \sim 10$ | ${10}^5$ | A | | $11 \sim 12$ | ${10}^5$ | B | | $13 \sim 16$ | ${10}^5$ | 无 | | $17 \sim 20$ | $5 \times {10}^5$ | 无 | 特殊性质 A：$c_i = 0$。 特殊性质 B：$\mathit{fa}_i = \lfloor \frac{i}{2} \rfloor$。