방송망

시간 제한2초메모리 제한128 MB

요약
루트가 있는 트리에서 설치할 선을 골라 사용자 요금 합이 설치 비용 합보다 작지 않게 유지하면서 서비스 가능한 사용자 수를 최대화하는 트리 냅색 DP 문제입니다.
난이도

어려움10점 중 8점

유형
동적 계획법, 트리, DFS, 재귀
정답자
아직 제출이 없습니다

문제

한 방송사가 유선 방송망을 설치하려고 한다. 방송망은 방송국을 루트로 하는 트리이다. 터미널 노드는 사용자이고, 터미널이 아닌 노드는 방송 신호를 전달하는 송신기이다. 루트는 방송국이면서 송신기이며, 루트도 터미널도 아닌 노드는 중간 송신기이다.

각 간선에는 방송 라인을 설치하는 비용이 있다. 총 방송 비용은 설치한 모든 라인의 비용 합이다.

사용자마다 방송을 시청할 때 지불하는 시청료가 미리 정해져 있다. 방송국에서 어떤 사용자까지 이어지는 모든 라인을 설치하면 그 사용자에게 방송을 제공하고 시청료를 받을 수 있다.

설치할 방송 라인을 적절히 골라 총 시청료에서 총 방송 비용을 뺀 값이 음수가 되지 않게 하면서, 방송을 제공할 수 있는 사용자 수의 최댓값을 구하라.

입력

첫 줄에 N과 M이 주어진다. (2 ≤ N ≤ 3,000, 1 ≤ M ≤ N-1) N은 트리의 전체 노드 수, M은 터미널 노드 수이다. 루트는 1번이다. 루트가 아닌 송신기는 2번부터 N-M번까지이고, 사용자(터미널 노드)는 N-M+1번부터 N번까지이다.

다음 N-M개의 줄에는 각 송신기 1, 2, ..., N-M의 정보가 순서대로 주어진다.

K A1 C1 A2 C2 ... AK CK

K는 해당 송신기가 직접 연결하는 자식 노드 수이다. Ai는 자식 노드 번호이고, Ci는 그 노드로 가는 방송 라인의 설치 비용이다.

마지막 M개의 줄에는 N-M+1번 사용자부터 N번 사용자까지의 시청료가 순서대로 주어진다.

출력

손해를 보지 않도록 방송을 제공할 수 있는 최대 사용자 수를 출력한다.

예제3

  1. 예제 1

    입력
    5 3
2 2 2 5 3
2 3 2 4 3
3 4 2
    예상 출력
    2

  2. 예제 2

    입력
    5 3
2 2 2 5 3
2 3 2 4 3
4 4 2
    예상 출력
    3

  3. 예제 3

    입력
    9 6
3 2 2 3 2 9 3
2 4 2 5 2
3 6 2 7 2 8 2
4 3 3 3 1 1
    예상 출력
    5