여행

시간 제한7초메모리 제한2048 MB

요약

노드마다 값이 적힌 트리에서 같은 노드를 두 번 방문하지 않고 한 개 이상의 노드를 골라 얻을 수 있는 최대 합을 구합니다.

난이도: 보통10점 중 4점
유형: 트리, 동적 계획법, DFS
정답자: 아직 제출이 없습니다

문제

Jimmy는 Treenidad and Treebago 나라로 여행을 간다. 이 나라 사람들은 나무에 푹 빠져서 나라 자체를 나무 모양으로 만들었다. 신중한 여행 계획자인 Jimmy는 여행에서 얻는 총 매력도를 최대로 하려면 어느 도시를 방문해야 하는지 미리 알고 싶어 한다. 도시의 매력도는 음수일 수도 있는 정수이다. Jimmy는 비자를 받느라 고생을 많이 했으므로 최소한 도시 한 곳은 방문하려고 한다. 여행은 어느 도시에서든 시작할 수 있다. 나라를 여행할 때 같은 도시를 두 번 방문해서는 안 된다.

입력

첫 줄에 도시 수를 나타내는 정수 $1\leq n \leq 10^6$ 이 주어진다. 이어서 $n$ 개의 줄이 주어지며, 첫 번째 줄은 트리의 루트를 나타낸다. 이후 각 줄에는 트리의 한 노드의 속성을 나타내는 두 정수 $V$ 와 $C$ 가 주어진다.

$V$ 는 그 노드의 값이며, $-2^{31} \leq V < 2^{31}$ 이다.
$C$ 는 그 노드의 자식 수이며, $0 \leq C < 10^6$ 이다.

그 뒤로 $C$ 개의 줄이 이어지며, 각 줄은 자식 트리를 재귀적으로 정의한다. 트리의 높이는 990 이하임이 보장된다.

출력

Jimmy가 얻을 수 있는 최대 매력도를 출력한다.

예제2

예제 1
입력
```
5
5 2
2 2
1 0
10 0
-1 0
```
예상 출력
```
17
```
예제 2
입력
```
7
1 3
3 2
5 0
6 0
2 1
3 0
4 0
```
예상 출력
```
15
```