← 返回题目列表

AtCoder · abc448_d

G. 整数重复路径

中文机器翻译题面 查看原题

分数: 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