問題一覧 > 通常問題

No.1295 Tree and Piece

レベル : / AI推定難易度 : 2450 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : 沙耶花 / テスター : QCFium
お気に入りにしたユーザー ProblemId : 4394 / 自分の提出
問題文最終更新日: 2020-11-21 19:14:58
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 275 (順位表) の他の問題:

Problem Statement

There is a tree with $N$ vertices. For each $i(1 \le i \le N-1)$, the $i$-th edge connects the $a_i$-th vertex and the $b_i$-th vertex.

Sayaka decided to play a game using this tree and one piece.
Below, a vertex on which the piece has been placed at least once during the game is called a "visited vertex", and any other vertex is called an "unvisited vertex".

At the beginning of the game, Sayaka places the piece on the $x$-th vertex. After that, she can perform the following two types of operations any number of times in any order.

  • Move the piece to the vertex with the smallest number among the unvisited vertices adjacent to the vertex on which the piece is currently placed
    (if no such vertex exists, do nothing)
  • Move the piece to the vertex with the smallest number among the visited vertices adjacent to the vertex on which the piece is currently placed
    (if no such vertex exists, do nothing)

The goal of this game is to make all vertices visited.
For each of the cases $x=1,2,...,N$, determine whether this can be achieved.

Input

$N$
$a_1\ b_1$
$\vdots$
$a_{N-1}\ b_{N-1}$

  • $2 \le N \le 10^5$
  • $1 \le a_i,b_i \le N$
  • All inputs are integers
  • The given graph is a tree

Output

Output $N$ lines.
On the $i$-th line, output Yes if the goal can be achieved for the case $x=i$, and No otherwise.
Print a newline at the end.

Sample

Sample 1
Input
6
1 5
2 5
3 4
4 5
6 5
Output
No
No
Yes
Yes
No
Yes

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。