問題一覧 > 通常問題

No.3189 Semifinal Stage

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 24
作問者 : 蜜蜂 / テスター : Mitarushi
お気に入りにしたユーザー ProblemId : 12318 / 自分の提出
問題文最終更新日: 2025-06-20 07:39:07
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$
$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$
Here, $\mathrm{Query}_i$ represents the content of the $i$-th query.

  • $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もしくは右上の雲マークをクリックしてアカウントを作成してください。