아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

도로 보수

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

요약
비용 합이 C 이하인 트리 경로 중 편익 합이 가장 큰 값을 구합니다.
난이도

어려움10점 중 8점

유형
트리, 분할 정복, 동적 계획법
정답자
아직 제출이 없습니다

문제

한 도시에 도로망이 있다. 도로는 저마다 두 구역을 잇는다. 이 도로망은 트리 구조여서 임의의 두 구역 사이에는 정확히 하나의 경로가 있다. 여기서 경로란 한 구역에서 다른 구역까지 이동하며 지나는 도로의 나열이다.

날마다 수많은 차량이 지나다니는 탓에 도로는 심하게 손상된다. 시 교통국은 도로를 정기적으로 보수한다. 각 도로 RR에는 비용 cc와 이득 bb가 정해져 있다. 비용 cc를 들여 도로 RR을 보수하면 사회적 이득 bb를 얻는다.

한 경로에 속한 도로를 모두 보수한다고 하자. 이때 경로의 비용은 속한 도로의 비용 합이고, 경로의 이득은 속한 도로의 이득 합이다. 비용 상한 CC가 주어질 때, 비용이 CC 이하이면서 이득이 가장 큰 경로를 찾아라.

입력

프로그램은 표준 입력에서 읽는다. 입력은 TT개의 테스트 케이스로 이루어지고, 첫 줄에 테스트 케이스의 개수 TT가 주어진다.

각 테스트 케이스의 첫 줄에는 도로망의 구역 수 nn이 주어진다 (2≤n≤220002 \le n \le 22000). 구역에는 11부터 nn까지 번호가 매겨져 있고, 도로는 언제나 정확히 n−1n-1개다. 이어지는 n−1n-1개의 줄에는 각각 네 정수 α\alpha, β\beta, cc, bb가 주어진다. 이는 구역 α\alpha와 β\beta를 잇는 도로의 비용이 cc이고 이득이 bb라는 뜻이다 (1≤α,β≤n1 \le \alpha, \beta \le n, 1≤c,b≤10001 \le c, b \le 1000). 마지막 줄에는 비용 상한 CC가 주어진다 (1≤C≤2×1071 \le C \le 2 \times 10^7).

출력

프로그램은 표준 출력에 쓴다. 테스트 케이스마다 한 줄씩 출력한다. 각 줄에는 비용이 CC 이하인 경로가 얻을 수 있는 최대 이득을 정수 하나로 출력한다. 그런 경로가 없으면 00을 출력한다.

예제2

  1. 예제 1

    입력
    2
11
1 2 2 2
2 3 1 4
3 4 3 6
3 5 2 2
5 6 1 4
5 8 3 3
6 7 5 1
8 9 2 4
9 10 2 1
9 11 3 2
8
18
1 9 1 2
9 14 2 3
10 14 6 2
2 9 5 2
3 10 1 3
4 11 2 6
11 15 3 3
12 15 4 4
5 12 1 5
6 12 2 6
17 18 3 4
16 18 2 5
7 13 2 3
13 16 1 2
8 16 1 2
15 17 4 1
14 17 2 3
10
    예상 출력
    13
18

  2. 예제 2

    입력
    1
2
1 2 1 1
1
    예상 출력
    1