No.3189 Semifinal Stage
問題文最終更新日: 2025-06-20 07:39:07
English (AI translation)
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 471
(順位表)
の他の問題:
Problem Statement
You are given a tree with $N$ vertices. The $i$-th edge connects vertices $U_i$ and $V_i$.
Initially, all vertices are painted white. Process $Q$ queries.
Each query has one of the following forms.
1 v: If the color of vertex $v$ immediately before the query is white, change it to black; if it is black, change it to white.2 v: Output the minimum possible value of the distance between vertex $v$ and a black vertex. It is guaranteed that a black vertex exists at the time of this query.
Input
$N$Here, $\mathrm{Query}_i$ represents the content of the $i$-th query.
$U_1\ \ V_1$
$U_2\ \ V_2$
$\vdots$
$U_{N - 1}\ \ V_{N - 1}$
$Q$
$\mathrm{Query}_1$
$\mathrm{Query}_2$
$\vdots$
$\mathrm{Query}_Q$
- $2 \leq N \leq 10^5$
- $1 \leq U_i < V_i \leq N$
- $1 \leq Q \leq 10^5$
- $1 \leq v \leq N$
- All input values are integers.
- The given graph is a tree.
- A black vertex exists at the time of each query starting with
2.
Output
For each query starting with 2, output the required value, followed by a newline.
Sample
Sample 1
Input
5
1 2
2 3
2 4
3 5
7
1 4
2 5
2 1
1 3
2 3
1 4
2 4
Output
3
2
0
2
For example, for the query 2 5, the optimal value is $3$, the distance between vertex $5$ and vertex $4$.
Sample 2
Input
2
1 2
5
1 2
2 1
2 2
1 1
2 1
Output
1
0
0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
蜜蜂