分数: 400 点
问题陈述
你有一棵树 N 顶点编号 1,2,\dots,N。的 i第一条边连接顶点 U_i 和 V_i.
每个顶点 i 有一个整数
上面写着 A_i 。
为大家解答以下问题 k=1,2,\dots,N.
- 问题:来自顶点的简单路径(不会多次访问同一顶点的路径)上的顶点之间 1 到顶点 k,如果存在两个不同的顶点且其上写有相同的整数,则输出
Yes;否则,输出No.- 可以证明,连接树上两个顶点的简单路径是唯一的。
约束
- 所有输入值均为整数。
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 1 \le U_i, V_i \le N
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
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
5 1 3 2 1 2 1 2 1 3 3 4 3 5
示例输出 1
No No No Yes Yes
- 对于 k=1:从顶点开始的路径 1 到顶点 1 仅包含顶点 1。由于路径仅由一个顶点组成,因此答案为
No. - 对于 k=2:从顶点开始的路径 1 到顶点 2 包含顶点 1,2,带有整数
上面分别写着 1,3 。因此,答案是
上面分别写着
No. - 对于 k=3:从顶点开始的路径 1 到顶点 3 包含顶点 1,3,带有整数
上面分别写着 1,2 。因此,答案是
上面分别写着
No. - 对于 k=4:从顶点开始的路径 1 到顶点 4 包含顶点 1,3,4,带有整数
上面分别写着 1,2,1 。由于顶点
路径上的 1 和 4 具有相同的整数
上面写着 1 ,答案是
Yes. - 对于 k=5:从顶点开始的路径 1 到顶点 5 包含顶点 1,3,5,带有整数
上面分别写着 1,2,2 。由于顶点
路径上的 3 和 5 具有相同的整数
上面写着 2 ,答案是
Yes.
示例输入 2
2 1000000000 1000000000 2 1
示例输出 2
No Yes
示例输入 3
10 10 7 3 9 1 3 8 5 7 10 3 6 8 6 6 1 9 7 7 10 5 4 4 2 10 2 1 9
示例输出 3
No Yes Yes Yes Yes No No No No Yes