다다스는 여러 패키지에 의존하는 프로젝트를 관리하고 있다. 프로젝트의 의존성 구조는 번 정점을 루트로 하는 트리로 주어진다. 번 정점은 프로젝트 자체이고, 나머지 정점은 패키지를 나타낸다.
각 패키지에는 보안 취약점이 존재할 수도 있다. 취약점을 해결하기 위해 다음 두 작업을 수행할 수 있다.
--force 수정: 패키지 를 강제로 업데이트한다. 비용은 이며, 와 의 모든 자손에 존재하는 취약점이 해결된다. 자체에 취약점이 없어도 이 작업을 수행할 수 있다.모든 작업의 적용 범위는 처음 주어진 트리를 기준으로 한다. 작업을 수행해도 트리의 구조와 각 작업의 비용은 변하지 않으며, 새로운 취약점이 생기거나 이미 해결된 취약점이 다시 발생하지 않는다.
--force 수정은 최대 번 수행할 수 있다. 일반 수정의 횟수에는 제한이 없다. 번 정점에는 어떤 수정도 수행할 수 없다.
모든 취약점을 해결하는 데 필요한 최소 비용을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 모든 취약점을 해결하는 데 필요한 최소 비용을 한 줄에 출력한다.
첫 번째 테스트 케이스에서는 번 패키지에 --force 수정을 수행해 번 패키지의 취약점을 비용 로 해결할 수 있다. 또한 번 패키지에 --force 수정을 수행하면 비용 이 든다. 총 비용은 이다.
각 케이스는 다음과 같은 형식으로 주어진다.
각 번 간선은 번 정점과 번 정점을 잇는다. 부모와 자식의 관계는 번 정점을 루트로 정했을 때를 기준으로 한다.
이면 번 패키지에 취약점이 존재하고, 이면 존재하지 않는다.
는 번 패키지에 일반 수정을 수행하는 비용이다. 취약점이 없는 정점에서는 이다.
는 번 패키지에 --force 수정을 수행하는 비용이다.
| 4 | 50 | 추가적인 제약이 없다. |