Statement
题面语言
다다스는 여러 패키지에 의존하는 프로젝트를 관리하고 있다. 프로젝트의 의존성 구조는 번 정점을 루트로 하는 트리로 주어진다. 번 정점은 프로젝트 자체이고, 나머지 정점은 패키지를 나타낸다.
각 패키지에는 보안 취약점이 존재할 수도 있다. 취약점을 해결하기 위해 다음 두 작업을 수행할 수 있다.
- 일반 수정: 취약점이 있는 패키지 를 수정한다. 비용은 이며, 의 취약점만 해결된다.
--force수정: 패키지 를 강제로 업데이트한다. 비용은 이며, 와 의 모든 자손에 존재하는 취약점이 해결된다. 자체에 취약점이 없어도 이 작업을 수행할 수 있다.
모든 작업의 적용 범위는 처음 주어진 트리를 기준으로 한다. 작업을 수행해도 트리의 구조와 각 작업의 비용은 변하지 않으며, 새로운 취약점이 생기거나 이미 해결된 취약점이 다시 발생하지 않는다.
--force 수정은 최대 번 수행할 수 있다. 일반 수정의 횟수에는 제한이 없다. 번 정점에는 어떤 수정도 수행할 수 없다.
모든 취약점을 해결하는 데 필요한 최소 비용을 구하여라.
Input
입력은 다음과 같은 형식으로 주어진다.
Output
각 테스트 케이스마다 모든 취약점을 해결하는 데 필요한 최소 비용을 한 줄에 출력한다.
Constraints
- .
- .
- .
Subtasks
Samples
样例输入
3
6 2
1 2
1 3
2 4
2 5
3 6
0 0 0 1 1 1
0 0 0 7 6 5
8 10 4 4 3
5 1
1 2
2 3
2 4
2 5
0 0 1 1 1
0 0 3 4 5
100 10 10 10
7 1
1 2
1 3
2 4
2 5
4 6
3 7
0 0 0 0 1 1 1
0 0 0 0 6 8 2
15 100 7 6 8 2
样例输出
11
12
15
첫 번째 테스트 케이스에서는 번 패키지에 --force 수정을 수행해 번 패키지의 취약점을 비용 로 해결할 수 있다. 또한 번 패키지에 --force 수정을 수행하면 비용 이 든다. 총 비용은 이다.