P15761 [JAG 2025 Summer Camp #1] Colored Tree and Path

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.