F - XOR Tree

Contest Duration: 2018-02-03(Sat) 14:00 - 2018-02-03(Sat) 19:00 (local time) (300 minutes) Back to Home

F - XOR Tree Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : $1000$ 点

問題文

$N$ 頂点の木が与えられます。頂点には $0$ から $N-1$ の番号がついています。辺は $1$ から $N-1$ までの番号がついていて、辺 $i$ は頂点 $x_i$ と $y_i$ をつなぎ、また $a_i$ という値を保持しています。あなたは以下の操作を何回でもすることが出来ます:

ある単純pathとある非負整数 $x$ を選び、そのpathを構成する各辺 $e$ について、 $a_e ← a_e ⊕ x$ (⊕ は xor)と変化させる。

目標はすべての辺 $e$ について $a_e = 0$ とすることです。目標を達成するために必要な最小の操作回数を求めてください。

制約

$2 ≤ N ≤ 10^5$
$0 ≤ x_i,y_i ≤ N-1$
$0 ≤ a_i ≤ 15$
与えられるグラフは木
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $x_1$   $y_1$   $a_1$ 
 $x_2$   $y_2$   $a_2$ 
 $:$ 
 $x_{N-1}$   $y_{N-1}$   $a_{N-1}$

出力

目標を達成するために必要な操作回数の最小値を出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

以下のようにして三回で目標を達成できます。

まず、頂点 $1,2$ を結ぶ path に対して $x=1$ で操作する
次に、頂点 $2,3$ を結ぶ path に対して $x=2$ で操作する
最後に、頂点 $0,4$ を結ぶ path に対して $x=4$ で操作する

入力例 2Copy

Copy

2
1 0 0

出力例 2Copy

Copy

Score : $1000$ points

Problem Statement

You are given a tree with $N$ vertices. The vertices are numbered $0$ through $N-1$ , and the edges are numbered $1$ through $N-1$ . Edge $i$ connects Vertex $x_i$ and $y_i$ , and has a value $a_i$ . You can perform the following operation any number of times:

Choose a simple path and a non-negative integer $x$ , then for each edge $e$ that belongs to the path, change $a_e$ by executing $a_e ← a_e ⊕ x$ (⊕ denotes XOR).

Your objective is to have $a_e = 0$ for all edges $e$ . Find the minimum number of operations required to achieve it.

Constraints

$2 ≤ N ≤ 10^5$
$0 ≤ x_i,y_i ≤ N-1$
$0 ≤ a_i ≤ 15$
The given graph is a tree.
All input values are integers.

Input

Input is given from Standard Input in the following format:

 $N$ 
 $x_1$   $y_1$   $a_1$ 
 $x_2$   $y_2$   $a_2$ 
 $:$ 
 $x_{N-1}$   $y_{N-1}$   $a_{N-1}$

Output

Find the minimum number of operations required to achieve the objective.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

The objective can be achieved in three operations, as follows:

First, choose the path connecting Vertex $1, 2$ , and $x = 1$ .
Then, choose the path connecting Vertex $2, 3$ , and $x = 2$ .
Lastly, choose the path connecting Vertex $0, 4$ , and $x = 4$ .

Sample Input 2Copy

Copy

2
1 0 0

Sample Output 2Copy

Copy