問題一覧 > 通常問題

No.3769 Even Contraction

レベル : / AI推定難易度 : 2325 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 4
作問者 : apricity / テスター : marc2825
お気に入りにしたユーザー ProblemId : 14075 / 自分の提出
問題文最終更新日: 2026-10-15 05:44:33
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 518 (順位表) の他の問題:

Problem Statement

You are given a tree with $N$ vertices. The vertices are numbered from $1$ to $N$, and the $i$-th edge connects vertex $u_i$ and vertex $v_i$.

In addition, an integer $A_i$ is written on vertex $i$. Here, $A_i$ is one of $0,1,2$.

Consider performing the following operation on this tree.

  • Choose $1$ edge. However, only an edge such that the integers $x,y$ written on the $2$ vertices it connects have the same parity can be chosen. Contract the chosen edge, and write $\dfrac{x+y}{2}$ on the new vertex created by the contraction.

Find the maximum number of times the operation can be performed.

Supplementary note on contraction More precisely, when the edge connecting vertex $u$ and vertex $v$ is chosen in the operation, the following is done.
  • Let $x,y$ be the integers written on vertices $u,v$, respectively. Add a new vertex $w$ on which the integer $\dfrac{x+y}{2}$ is written.
  • For every edge that has vertex $u$ or $v$ as an endpoint, other than the edge connecting vertex $u$ and vertex $v$, do the following.
    • Let $t$ be the endpoint that is neither $u$ nor $v$. Add an edge connecting vertex $t$ and vertex $w$.
  • Delete vertices $u,v$ and all edges that have at least one of $u,v$ as an endpoint.

Input

$N$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_{N-1}\ v_{N-1}$
$A_1\ A_2\ \dots\ A_N$
  • All input values are integers.
  • $2 \leq N \leq 10^5$
  • $1 \leq u_i, v_i \leq N$
  • $\color{red}A_i \in \lbrace 0,1,2\rbrace$
  • The given graph is a tree.

Output

Output the maximum number of times the operation can be performed.

Sample

Sample 1
Input
5
1 2
2 3
2 4
4 5
0 0 2 1 0
Output
3

The maximum number of operations is $3$. An example of $3$ operations is illustrated below. The red edge is the edge chosen at each step.

After $3$ operations, the only remaining edge connects a vertex with $0$ written on it and a vertex with $1$ written on it. Since their parities differ, no further operation can be performed.

Sample 2
Input
2
1 2
0 1
Output
0

No operation can be performed even once.

Sample 3
Input
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
Output
6

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