정점이 개인 루트 있는 트리가 주어진다. 루트는 번 정점이다.
리프가 아닌 각 정점 에 대해, 의 자식들을 한 줄로 나열한 순서를 하나 정할 수 있다. 이 순서는 공을 넣기 전에 정하며, 공이 이동하는 동안에는 바꿀 수 없다.
공을 루트에 하나씩 넣는다. 어떤 정점 에 들어온 공 중 번째 공을 생각하자. 정점 의 자식 수를 라 하면, 이 공은 정해 둔 순서에서
번째 자식으로 이동한다. 공은 리프에 도착하면 멈춘다.
공 하나가 리프 에 도착할 때마다 점을 얻는다. 는 음수일 수도 있다.
각 에 대해, 루트에 공을 개 넣었을 때 얻을 수 있는 총점의 최댓값을 구하여라. 자식들의 순서는 마다 서로 다르게 정해도 된다.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 한 줄에 개의 정수 를 공백으로 구분하여 출력한다.
각 에 대해 자식 순서를 하나 정한 뒤 공의 이동을 규칙대로 진행하면 된다. 가장 높은 총점을 만드는 순서를 선택하면 출력과 같은 값을 얻는다.
각 케이스는 다음과 같은 형식으로 주어진다.
각 에 대해 번 정점과 번 정점을 잇는 간선이 있다. 주어진 그래프는 트리이다. 트리의 루트는 번 정점이다.
리프가 아닌 정점의 는 답에 영향을 주지 않는다.
는 루트에 공을 개 넣었을 때 얻을 수 있는 총점의 최댓값이어야 한다.
| 4 | 18 | . |
| 5 | 18 | 리프가 아닌 모든 정점의 자식 수가 이상이다. |
| 6 | 32 | 추가적인 제약이 없다. |
