Problem Description

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

Input Format

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.

Output Format

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

5
1 2 3 3
2 2 4 3
5
1 3
1 1
2 4 4 2
2 3 1 1
1 2

8
8
7

Hint

Constraints: $1\leq n,m\leq 100000$, $1\leq e_i\leq 10000$.

Translated by ChatGPT 5