D - Integer-duplicated Path Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

頂点 1,2,\dots,N の N 頂点からなる木が与えられます。この木の辺のうち i 本目は頂点 U_i と頂点 V_i を結びます。
頂点 i には整数 A_i が書かれています。

全ての k=1,2,\dots,N について以下の問題に答えてください。

  • 問題: 頂点 1 から頂点 k への単純なパス (同じ頂点を複数回通らないパス) に含まれる頂点について、同じ整数の書かれた異なる 2 頂点の組が存在すれば Yes 、そうでないなら No と答えよ。
    • なお、木上の 2 つの頂点を結ぶ単純なパスが一意に定まることは証明できる。

制約

  • 入力は全て整数
  • 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 です。パスが 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

Score : 400 points

Problem Statement

You are given a tree with N vertices numbered 1,2,\dots,N. The i-th edge connects vertices U_i and V_i.
Each vertex i has an integer A_i written on it.

Answer the following problem for all k=1,2,\dots,N.

  • Problem: Among the vertices on the simple path (a path that does not visit the same vertex more than once) from vertex 1 to vertex k, if there exist two distinct vertices with the same integer written on them, output Yes; otherwise, output No.
    • It can be proved that the simple path connecting two vertices on a tree is unique.

Constraints

  • All input values are integers.
  • 2 \le N \le 2 \times 10^5
  • 1 \le A_i \le 10^9
  • 1 \le U_i, V_i \le N
  • The given graph is a tree.

Input

The input is given from Standard Input in the following format:

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

Output

Output N lines.
The i-th line should contain the answer to the problem for k=i.

Sample Input 1

5
1 3 2 1 2
1 2
1 3
3 4
3 5

Sample Output 1

No
No
No
Yes
Yes
  • For k=1: the path from vertex 1 to vertex 1 contains only vertex 1. Since the path consists of only one vertex, the answer is No.
  • For k=2: the path from vertex 1 to vertex 2 contains vertices 1,2, with integers 1,3 written on them respectively. Thus, the answer is No.
  • For k=3: the path from vertex 1 to vertex 3 contains vertices 1,3, with integers 1,2 written on them respectively. Thus, the answer is No.
  • For k=4: the path from vertex 1 to vertex 4 contains vertices 1,3,4, with integers 1,2,1 written on them respectively. Since vertices 1 and 4 on the path have the same integer 1 written on them, the answer is Yes.
  • For k=5: the path from vertex 1 to vertex 5 contains vertices 1,3,5, with integers 1,2,2 written on them respectively. Since vertices 3 and 5 on the path have the same integer 2 written on them, the answer is Yes.

Sample Input 2

2
1000000000 1000000000
2 1

Sample Output 2

No
Yes

Sample Input 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

Sample Output 3

No
Yes
Yes
Yes
Yes
No
No
No
No
Yes