题目描述

You are given a tree with $N$ vertices, numbered $1$ through $N$. Edge $i$ connects vertices $a_i$ and $b_i$. Each vertex $i$ is assigned a color $c_i$.

You are asked to process $Q$ queries. In each query, four integers $u_1, v_1, u_2, v_2$ are given.

For each query, determine the maximum integer $K$ ($0 \leq K \leq N$) such that the following condition holds:

• For every $j = 1, 2, \ldots, K$, the number of vertices of color $j$ on the path from $u_1$ to $v_1$ is equal to the number of vertices of color $j$ on the path from $u_2$ to $v_2$.

输入格式

The input is given in the following format:

$$\begin{aligned} & N \\ & a_1 \ b_1 \\ & a_2 \ b_2 \\ & \vdots \\ & a_{N-1} \ b_{N-1} \\ & c_1 \ c_2 \ \ldots \ c_N \\ & Q \\ & \text{Query}_1 \\ & \text{Query}_2 \\ & \vdots \\ & \text{Query}_Q \end{aligned}$$

Each Query is given in the following format:

$$u_1 \ v_1 \ u_2 \ v_2$$

• $1 \leq N \leq 100\ 000$
• $1 \leq a_i, b_i \leq N$ ($1 \leq i \leq N - 1$)
• $1 \leq c_i \leq N$ ($1 \leq i \leq N$)
• $1 \leq Q \leq 100\ 000$
• $1 \leq u_1, v_1, u_2, v_2 \leq N$ ($1 \leq i \leq Q$)
• The given graph is a tree.
• All input values are integers.

输出格式

Output $Q$ lines. On the $i$-th line ($1 \leq i \leq Q$), output the answer for the $i$-th query.

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

0
6
6
0