#576 보안 취약점 패치

Statement

問題文の言語

다다스는 여러 패키지에 의존하는 프로젝트를 관리하고 있다. 프로젝트의 의존성 구조는 $1$ 번 정점을 루트로 하는 트리로 주어진다. $1$ 번 정점은 프로젝트 자체이고, 나머지 정점은 패키지를 나타낸다.

각 패키지에는 보안 취약점이 존재할 수도 있다. 취약점을 해결하기 위해 다음 두 작업을 수행할 수 있다.

일반 수정: 취약점이 있는 패키지 $v$ 를 수정한다. 비용은 $C_v$ 이며, $v$ 의 취약점만 해결된다.
--force 수정: 패키지 $v$ 를 강제로 업데이트한다. 비용은 $F_v$ 이며, 와 의 모든 자손에 존재하는 취약점이 해결된다. 자체에 취약점이 없어도 이 작업을 수행할 수 있다.

모든 작업의 적용 범위는 처음 주어진 트리를 기준으로 한다. 작업을 수행해도 트리의 구조와 각 작업의 비용은 변하지 않으며, 새로운 취약점이 생기거나 이미 해결된 취약점이 다시 발생하지 않는다.

--force 수정은 최대 $K$ 번 수행할 수 있다. 일반 수정의 횟수에는 제한이 없다. $1$ 번 정점에는 어떤 수정도 수행할 수 없다.

모든 취약점을 해결하는 데 필요한 최소 비용을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 모든 취약점을 해결하는 데 필요한 최소 비용을 한 줄에 출력한다.

入力例

3
2
2
3
4
5
6
0 0 1 1 1
0 0 7 6 5
10 4 4 3
1
2
3
4
5
0 1 1 1
0 3 4 5
10 10 10
1
2
3
4
5
6
7
0 0 0 1 1 1
0 0 0 6 8 2
100 7 6 8 2

出力例

11
12
15

첫 번째 테스트 케이스에서는 $2$ 번 패키지에 --force 수정을 수행해 $4,5$ 번 패키지의 취약점을 비용 $8$ 로 해결할 수 있다. 또한 $6$ 번 패키지에 --force 수정을 수행하면 비용 $3$ 이 든다. 총 비용은 이다.