P10776 BZOJ3914 Jabby's shadows

You are given an unrooted tree with $n$ nodes. The tree edges have weights. Each node has one of two colors. Initially, all nodes are black. Black is $1$, and white is $2$. Each edge has a positive weight. You need to maintain $m$ operations: - `1 u`: Query the diameter of the monochromatic connected component (connected block with the same color) that contains node $u$. If it is $0$, output `QwQ`. - `2 u v c`: Recolor (cover) the path from $u$ to $v$ with color $c$.

The first line contains a positive integer $n$, the number of nodes in the tree. The second line contains $n-1$ positive integers $f_i$, the parent of nodes $2 \sim n$. The third line contains $n-1$ positive integers $e_i$, the edge weight of the edge from node $2 \sim n$ to its parent. The fourth line contains a positive integer $m$, the number of operations. The next $m$ lines describe the operations in order.

For each operation of type $1$, output one line as the answer.

Constraints: $1\leq n,m\leq 100000$, $1\leq e_i\leq 10000$. Translated by ChatGPT 5