No.1295 Tree and Piece
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
沙耶花
QCFium