P10065 [SNOI2024] Character Tree

You are given a rooted tree with $n$ nodes, with node $1$ as the root. Each edge has a character $c \in \{0, 1\}$. Let $S_u$ be the string formed by writing down, in order, the characters on the path from the root to node $u$. It is guaranteed that, for each node, the characters on the edges from this node to its children are pairwise distinct. For each node $u$, there is a value $\mathit{val}_u$ and a limit $a_u$. For a node $u$, if a node $v$ satisfies that $S_u$ is a suffix of $S_v$, then we call $v$ an extension node of $u$. Alice has a string $S$. Initially, let $S = S_u$. Now she can delete some suffix characters so that $S$ becomes $S'$, and then tell $S'$ to Bob. Bob receives a string $S'$. He needs to append some characters after $S'$ to obtain $S''$. For an extension node $v$ of some $u$, if $S'' = S_v$ and $\lvert S' \rvert \ge a_v$, then Bob gains profit $\mathit{val}_v$. Of course, Bob can perform such an operation only once, so he will choose, among all valid $v$, the one with the maximum $\mathit{val}_v$. If there is no valid $v$, Bob can gain only $0$. Now Alice wants to know: among all $\lvert S \rvert + 1$ deletion choices (deleting $0 \sim \lvert S \rvert$ characters), what is the sum of the profits Bob can obtain? For each $u$, you need to answer Alice’s query. Formally: For each node $u$, compute $\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$。 In particular, if for some $u$ there is no $v$ satisfying the conditions, then $\max = 0$. Here $S[l, r]$ denotes the substring consisting of the $l$-th to the $r$-th characters of string $S$. In particular, $S[x + 1, x]$ denotes the empty string. $\lvert S \rvert$ denotes the length of $S$, and $\land$ means “and”.

Multiple test cases. The first line contains an integer $T$, denoting the number of test cases. For each test case, the first line contains a positive integer $n$, denoting the number of nodes. The next $n - 1$ lines each contain two integers $\mathit{fa}_i, c_i$, denoting the parent index of node $i$ and the character on the edge. The next line contains $n$ positive integers $\mathit{val}_1, \mathit{val}_2, \ldots, \mathit{val}_n$. The next line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$.

Output one line with $n$ integers $\mathit{ans}_1, \mathit{ans}_2, \ldots, \mathit{ans}_n$.

**[Sample #1 Explanation]** The following table shows, for fixed $u$ and $i$, the maximum value of $\mathit{val}_v$ in the formula. | | $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$ | --- **[Sample #2]** See the attachments `tree/tree2.in` and `tree/tree2.ans`. This sample satisfies the constraints of test points $3 \sim 5$. --- **[Sample #3]** See the attachments `tree/tree3.in` and `tree/tree3.ans`. This sample satisfies the constraints of test points $9 \sim 10$. --- **[Sample #4]** See the attachments `tree/tree4.in` and `tree/tree4.ans`. This sample satisfies the constraints of test points $11 \sim 12$. --- **[Constraints]** For all testdata, it is guaranteed that $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 \in \{0, 1\}$, and $0 \le a_i \le n$. Specifically: | Test Point ID | $n \le$ | Special Property | |:-:|:-:|:-:| | $1 \sim 2$ | $100$ | None | | $3 \sim 5$ | $2 \times {10}^3$ | None | | $6 \sim 8$ | ${10}^4$ | None | | $9 \sim 10$ | ${10}^5$ | A | | $11 \sim 12$ | ${10}^5$ | B | | $13 \sim 16$ | ${10}^5$ | None | | $17 \sim 20$ | $5 \times {10}^5$ | None | Special property A: $c_i = 0$. Special property B: $\mathit{fa}_i = \lfloor \frac{i}{2} \rfloor$. Translated by ChatGPT 5