25910번 - 게이트웨이 정하기

$N$개의 노드와 $N-1$개의 양방향 링크로 이루어져 있는 트리 구조의 네트워크가 있다.

율전이는 외부 네트워크로부터 데이터를 받아서 노드 전체에 이 데이터를 전달하려고 한다. 데이터는 $20$비트의 헤더 $X$를 포함하는데, 헤더는 링크를 지날 때마다 링크의 특성값과 XOR된 값으로 바뀌게 되고, 네트워크에 데이터를 전달하는 총 비용은 각 노드에 전달된 헤더의 $1$ 비트 개수의 합이 된다.

율전이는 외부 네트워크로부터 최초로 데이터를 받아 트리 네트워크에 전달할 게이트웨이 노드를 고르려고 하는데, 총 데이터 전달 비용을 최소로 하려고 한다. 율전이가 게이트웨이 노드를 잘 골랐을 때 구할 수 있는 총 데이터 전달 비용의 최솟값을 구하여라.

첫 번째 줄에 노드의 수 $N$, 데이터의 헤더 $X$가 공백으로 구분되어 주어진다. $(1 \le N \le 100\,000;$ $0 \le X < 2^{20})$

두 번째 줄부터 $N-1$개의 줄에 걸쳐 각 링크가 연결하는 두 노드 $A$, $B$ 그리고 링크의 특성값 $C$가 공백으로 구분되어 주어진다. $(0 \le C < 2^{20})$

입력으로 주어지는 모든 수는 정수이다.

총 데이터 전달 비용의 최솟값을 출력한다.