問題一覧 > 通常問題

No.3442 Good Vertex Connectivity

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 19
作問者 : 👑 potato167 / テスター : noya2
お気に入りにしたユーザー ProblemId : 13006 / 自分の提出
問題文最終更新日: 2026-02-21 03:46:12
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 492 (順位表) の他の問題:

Problem Statement

You are given a tree with $N$ vertices numbered $1, 2, \dots N$. The $i$-th edge connects vertex $A_{i}$ and vertex $B_{i}$.

Each vertex of the tree is painted white or black. Initially, vertex $i$ is painted white if $C_{i} = 0$ and black if $C_{i} = 1$.

You are given $Q$ queries; process them in the given order. Each query is one of the following $2$ types.

  • 1 v : Flip the color of vertex $v$ (white becomes black, and black becomes white).
  • 2 x y : Call a vertex $v$ a good vertex if it satisfies all of the following conditions. Output the minimum number of vertices of a connected subgraph containing all good vertices. (However, if no good vertex exists, output $0$.)
    • Vertex $v$ is painted black.
    • The simple path connecting vertex $v$ and vertex $x$ contains vertex $y$.

Constraints

  • $1\leq N\leq 2\times 10^{5}$
  • $1\leq A_{i} < B_{i}\leq N$
  • The given graph is a tree.
  • $C_{i}\in \{0, 1\}$
  • $1\leq Q\leq 2\times 10^{5}$
  • $1\leq v\leq N$
  • $1\leq x\leq N$
  • $1\leq y\leq N$
  • All input values are integers.

Input

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

$N$
$A_{1}$ $B_{1}$
$A_{2}$ $B_{2}$
$\vdots$
$A_{N - 1}$ $B_{N - 1}$
$C_{1}$ $C_{2}$ $\dots$ $C_{N}$
$Q$
$\mathrm{query}_{1}$
$\mathrm{query}_{2}$
$\vdots$
$\mathrm{query}_{Q}$

Each query $\mathrm{query}_{i}$ is given in one of the following formats.

$1$ $v$
$2$ $x$ $y$

Output

Following the instructions in the problem statement, output the answers to the queries, separated by newlines.

Sample

Sample 1
Input
10
1 2
1 3
2 4
2 5
3 6
3 7
6 8
6 9
9 10
1 0 1 0 1 0 1 0 1 0
10
2 1 1
2 4 2
2 8 2
1 5
2 8 2
1 3
2 10 3
1 1
2 1 1
2 6 9
Output
7
7
1
0
3
4
1

For the $1$st query, the set of indices of the good vertices is ${1,3,5,7,9}$. The subgraph corresponding to the vertex set ${1,2,3,5,6,7,9}$ is connected and contains all good vertices. Moreover, no "connected subgraph containing all good vertices" with fewer than $7$ vertices exists, so output $7$ for this query.

For the $5$th query, no good vertex exists, so output $0$ for this query.

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