게이트웨이 정하기

시간 제한1초메모리 제한1024 MB

요약

트리에서 각 간선이 XOR 특성값을 가지며 20비트 헤더 X가 주어질 때, 모든 노드에 전달된 헤더의 1 비트 개수 합이 최소가 되는 게이트웨이 노드를 골라 그 최솟값을 구한다.

난이도: 보통10점 중 6점
유형: 트리, DFS, 비트 연산, 그리디
정답자: 아직 제출이 없습니다

문제

$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})$

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

출력

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

예제3

예제 1
입력
```
1 5
```
예상 출력
```
2
```
예제 2
입력
```
3 1
1 2 1
1 3 1
```
예상 출력
```
1
```
예제 3
입력
```
5 5
1 2 10
1 3 7
3 4 1
1 5 11
```
예상 출력
```
7
```