금광을 찾아서

시간 제한4초메모리 제한512 MB

요약

각 간선마다 두 가지 길이 중 하나를 고르고, 정확히 k개의 간선에 첫 번째 길이를 쓸 때 가능한 트리 지름의 최솟값을 구합니다.

난이도: 어려움10점 중 8점
유형: 트리, 동적 계획법, 분할 정복
정답자: 아직 제출이 없습니다

문제

Sunset은 국경 마을에서 버려진 금광의 지도를 얻었다. 지도에 따르면 금광은 $n$ 개의 방이 $n-1$ 개의 양방향 터널로 연결된 트리 구조이다. 지도는 이상하게도 $i$ 번째 터널마다 두 수 $a_i$ 와 $b_i$ 가 적혀 있다. Sunset이 아는 것은 정확히 $k$ 개의 터널은 길이를 $a$ 에서 가져왔고, 나머지 $n-k-1$ 개의 터널은 길이를 $b$ 에서 가져왔다는 사실뿐이다.

내일 Sunset이 이 금광을 탐사한다. 그는 길을 잃을까 걱정하고 있다. 운이 좋다면 금광의 지름을 알려 달라. 즉, Sunset이 가진 정보로부터 지름 길이의 최솟값을 구하라.

입력

첫 줄에 테스트 케이스의 수 $T$ ( $1 \leq T \leq 10000$ )가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 방의 수 $n$ 과 파라미터 $k$ ( $2 \leq n \leq 20000$ , $0 \leq k \leq n - 1$ , $k \leq 20$ )가 정수 두 개로 주어진다.

이어지는 $n-1$ 개의 줄에는 정수 네 개 $u_i$ , $v_i$ , $a_i$ , $b_i$ ( $1 \leq u_i, v_i \leq n$ , $u_i \neq v_i$ , $1 \leq a_i, b_i \leq 10^9$ )가 주어진다. 이는 $u_i$ 번 방과 $v_i$ 번 방을 잇는 양방향 터널이며, 길이는 $a_i$ 또는 $b_i$ 이다.

모든 테스트 케이스의 $n$ 의 합은 200000 이하이다.

출력

각 테스트 케이스마다 지름 길이의 최솟값을 한 줄에 출력한다.

예제1

예제 1
입력
```
1
4 1
1 2 1 3
2 3 4 2
2 4 3 5
```
예상 출력
```
6
```