19433번 - Born Slippy 다국어

Professor Zhang has a rooted tree with vertices conveniently labeled by $1, 2, \ldots, n$. The $i$-th vertex has an integer weight $w_i$.

For each $s \in \{1, 2, \ldots, n\}$, Professor Zhang wants to find a sequence of vertices $v_1, v_2, \ldots, v_m$ such that:

• $v_1 = s$ and $v_i$ is the ancestor of $v_{i - 1}$ for each $1 < i \le m$,
• the value $f(s) = w_{v_1} + \sum\limits_{i = 2}^{m} (w_{v_i} \mathrm{op} w_{v_{i - 1}})$ is maximum possible. Here, operation $x \mathrm{op} y$ is the bitwise AND, OR, or XOR operation on two integers.

There are multiple test cases. The first line of input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ and a string $\mathrm{op}$ ($2 \le n \le 2^{16}$, $\mathrm{op} \in \{\mathtt{AND}, \mathtt{OR}, \mathtt{XOR}\}$): the number of vertices and the operation. The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($0 \le w_i < 2^{16}$). The third line contains $n - 1$ integers $p_2, p_3, \ldots, p_n$ ($1 \le p_i < i$) where $p_i$ is the parent of vertex $i$.

There are about $300$ test cases, and the sum of $n$ in all the test cases is no more than $10^6$.

For each test case, output the integer $S = (\sum\limits_{i = 1}^{n}{i \cdot f(i)})$ modulo $10^9 + 7$.