No.3442 Good Vertex Connectivity
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2