No.3769 Even Contraction
apricity
marc2825
問題文最終更新日: 2026-10-15 05:44:33
yukicoder contest 518
(順位表)
の他の問題:
問題文
$N$ 頂点の木が与えられます．頂点には $1$ から $N$ までの番号がついており， $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいます．
また，頂点 $i$ には整数 $A_i$ が書かれています．ここで $A_i$ は $0,1,2$ のいずれかです．
この木に対して次の操作を行うことを考えます．
- 辺を $1$ 本選ぶ．ただし，その辺が結ぶ $2$ つの頂点に書かれている整数 $x,y$ の偶奇が等しいもののみを選ぶことができる．選んだ辺を縮約し，縮約してできる新たな頂点に $\dfrac{x+y}{2}$ を書き込む．
操作を行うことのできる回数の最大値を求めてください．
縮約についての補足
操作で頂点 $u$ と頂点 $v$ を結ぶ辺を選ぶと，より正確には以下が行われます．- 頂点 $u,v$ に書かれた整数をそれぞれ $x,y$ として，新たに整数 $\dfrac{x+y}{2}$ が書かれた頂点 $w$ を追加する．
- 頂点 $u$ または $v$ を端点とする辺のうち，頂点 $u$ と頂点 $v$ を結ぶもの以外のすべてについて以下を行う．
- 端点のうち $u$ でも $v$ でもないものを $t$ として，頂点 $t$ と頂点 $w$ を結ぶ辺を追加する．
- 頂点 $u,v$ および， $u,v$ の少なくとも一方を端点とする辺をすべて削除する．
入力
$N$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_{N-1}\ v_{N-1}$
$A_1\ A_2\ \dots\ A_N$
- 入力はすべて整数．
- $2 \leq N \leq 10^5$
- $1 \leq u_i, v_i \leq N$
- $\color{red}A_i \in \lbrace 0,1,2\rbrace$
- 与えられるグラフは木である．
出力
操作を行うことのできる回数の最大値を出力してください．
サンプル
サンプル1
入力
5 1 2 2 3 2 4 4 5 0 0 2 1 0
出力
3
最大の操作回数は $3$ です．以下に $3$ 回の操作の一例を図示します．赤色の辺が各段階で選ぶ辺です．
$3$ 回の操作後，唯一存在する辺は $0$ が書かれた頂点と $1$ が書かれた頂点を結んでいます．偶奇が異なるのでこれ以上操作を行えません．
サンプル2
入力
2 1 2 0 1
出力
0
一回も操作を行えません．
サンプル3
入力
10 1 2 2 3 2 4 1 5 5 6 5 7 5 8 4 9 7 10 0 1 1 0 2 0 2 0 0 0
出力
6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。