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

给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。每个顶点 $i$ 被赋予一种颜色 $c_i$。 你需要处理 $Q$ 个询问。在每个询问中，会给出四个整数 $u_1, v_1, u_2, v_2$。 对于每个询问，确定最大的整数 $K$（$0 \leq K \leq N$），使得以下条件成立： - 对于每个 $j = 1, 2, \ldots, K$，从 $u_1$ 到 $v_1$ 的路径上颜色为 $j$ 的顶点数量，等于从 $u_2$ 到 $v_2$ 的路径上颜色为 $j$ 的顶点数量。

输入格式如下： $$\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}$$ 每个询问的格式如下： $$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$) - 给定的图是一棵树。 - 所有输入值均为整数。

输出 $Q$ 行。在第 $i$ 行（$1 \leq i \leq Q$），输出第 $i$ 个询问的答案。