AT_abc448_d.[ABC448D] Integer-duplicated Path

给定一棵有 $N$ 个结点的树，结点编号为 $1,2,\dots,N$。第 $i$ 条边连接结点 $U_i$ 和 $V_i$。每个结点 $i$ 上写有一个整数 $A_i$。

对于所有 $k=1,2,\dots,N$，请回答以下问题：

• 问题：在从结点 $1$ 到结点 $k$ 的简单路径（即不会经过同一个结点超过一次的路径）上，如果存在两个不同的结点上写着相同的整数，则输出 Yes；否则输出 No。
  • 可以证明，在树上连接任意两个结点的简单路径是唯一的。

输入按以下格式给出：

$N$ $A_1$ $A_2$ $\dots$ $A_N$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{N-1}$ $V_{N-1}$

输出 $N$ 行。
第 $i$ 行应输出对于 $k=i$ 时对应问题的答案。

样例解释 1

• 对于 $k=1$：路径为结点 $1$，只包含结点 $1$。由于路径上只有一个点，答案为 No。
• 对于 $k=2$：路径为结点 $1,2$，分别写着整数 $1,3$。答案为 No。
• 对于 $k=3$：路径为结点 $1,3$，分别写着整数 $1,2$。答案为 No。
• 对于 $k=4$：路径为结点 $1,3,4$，分别写着整数 $1,2,1$。结点 $1$ 和 $4$ 上写着相同的整数 $1$，答案为 Yes。
• 对于 $k=5$：路径为结点 $1,3,5$，分别写着整数 $1,2,2$。结点 $3$ 和 $5$ 上写着相同的整数 $2$，答案为 Yes。

数据范围

• 所有输入值均为整数。
• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• $1 \le U_i, V_i \le N$
• 给定的图是一棵树。

由 ChatGPT 5 翻译