F - Tree Game Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 16001600 点

問題文

NN 頂点からなる木があり、頂点には 11 から NN の番号がついています。 また、N−1N-1 本の辺の内、ii 番目の辺は頂点 aia_i と頂点 bib_i を結んでいます。

今、各頂点 ii には AiA_i 個の石が置いてあります。 高橋君と青木君はこの木を使ってゲームをすることにしました。

まず、高橋君が一つの頂点を選び、そこに駒を置きます。 その後、高橋君から始めて以下の操作を交互に繰り返します。

  • 今、駒がおいてある頂点から石を一つ取り除く。
  • その後、その頂点に隣接する頂点を一つ選び、そこに駒を動かす。

駒が置いてある頂点に石がなく、操作を行えない人が負けです。 高橋君がこのゲームに勝つために、最初に駒を置くことができる頂点をすべて求めてください。

制約

  • 2≦N≦30002 ≦ N ≦ 3000
  • 1≦ai,bi≦N1 ≦ a_i,b_i ≦ N
  • 0≦Ai≦1090 ≦ A_i ≦ 10^9
  • 与えられるグラフは木である。

入力

入力は以下の形式で標準入力から与えられる。

NN
A1A_1 A2A_2 … ANA_N
a1a_1 b1b_1
:
aN−1a_{N-1} bN−1b_{N-1}

出力

高橋君が最初に駒を置いて勝つことができる頂点の番号を昇順に一行に出力せよ。

入力例 1Copy

Copy
3
1 2 3
1 2
2 3

出力例 1Copy

Copy
2

高橋君が頂点 22 に駒を置いたとき、例えば以下のようにゲームが進みます。

  • 高橋君が駒を頂点 11 に動かす。このとき、各頂点にある石の個数は (1,1,3)(1,1,3) である。
  • 青木君が駒を頂点 22 に動かす。このとき、各頂点にある石の個数は (0,1,3)(0,1,3) である。
  • 高橋君が駒を頂点 11 に動かす。このとき、各頂点にある石の個数は (0,0,3)(0,0,3) である。
  • 青木君が石を取れないため、高橋君の勝ちとなる。

入力例 2Copy

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

出力例 2Copy

Copy
1 2

入力例 3Copy

Copy
3
1 1 1
1 2
2 3

出力例 3Copy

Copy



題意を満たす頂点が存在しない場合があることに注意してください。






Score : 16001600 points







Problem Statement
There is a tree with NN vertices, numbered 11 through NN.
The ii-th of the N−1N-1 edges connects vertices aia_i and bib_i.


Currently, there are AiA_i stones placed on vertex ii.
Takahashi and Aoki will play a game using this tree.


First, Takahashi will select a vertex and place a piece on it.
Then, starting from Takahashi, they will alternately perform the following operation:


    

  • Remove one stone from the vertex currently occupied by the piece.
    • 

  • Then, move the piece to a vertex that is adjacent to the currently occupied vertex.
    • 



The player who is left with no stone on the vertex occupied by the piece and thus cannot perform the operation, loses the game.
Find all the vertices vv such that Takahashi can place the piece on vv at the beginning and win the game.











Constraints
    

  • 2≦N≦30002 ≦ N ≦ 3000
    • 

  • 1≦ai,bi≦N1 ≦ a_i,b_i ≦ N
    • 

  • 0≦Ai≦1090 ≦ A_i ≦ 10^9
    • 

  • The given graph is a tree.
    • 

















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


NN
A1A_1 A2A_2 … ANA_N
a1a_1 b1b_1
:
aN−1a_{N-1} bN−1b_{N-1}












Output
Print the indices of the vertices vv such that Takahashi can place the piece on vv at the beginning and win the game, in a line, in ascending order.
















Sample Input 1Copy
Copy
3
1 2 3
1 2
2 3













Sample Output 1Copy
Copy
2




The following is one possible progress of the game when Takahashi places the piece on vertex 22:


    

  • Takahashi moves the piece to vertex 11. The number of the stones on each vertex is now: (1,1,3)(1,1,3).
    • 

  • Aoki moves the piece to vertex 22. The number of the stones on each vertex is now: (0,1,3)(0,1,3).
    • 

  • Takahashi moves the piece to vertex 11. The number of the stones on each vertex is now: (0,0,3)(0,0,3).
    • 

  • Aoki cannot take a stone from the vertex, and thus Takahashi wins.
    • 















Sample Input 2Copy
Copy
5
5 4 1 2 3
1 2
1 3
2 4
2 5













Sample Output 2Copy
Copy
1 2
















Sample Input 3Copy
Copy
3
1 1 1
1 2
2 3













Sample Output 3Copy
Copy



Note that the correct output may be an empty line.






		


		

		
	







		
			

			
			
			


	
	
	
		
	
	



		
		
		
	
 
	


 

	

			
	

	
2025-04-09 (Wed)
20:32:30 +00:00