문제
입력
첫 번째 줄에는 사과의 수 N이 주어진다. (1 ≤ N ≤ 300,000)
두 번째 줄부터 N개의 줄에는 구사과가 만들려고 하는 사과나무의 정보가 주어진다. 각 줄에는 각 줄기의 양 끝점의 번호와 줄기의 광도가 주어진다. 0번 지점은 새싹, 1~N번 지점은 사과를 의미하며 줄기의 광도는 1 이상 1,000,000 이하이다. 모든 줄기의 광도는 서로 다르다. 모든 줄기를 연결했을 때 새싹과 1~N번 사과가 모두 연결된다.
출력
첫 번째 줄에, 만들 수 있는 모든 사과나무의 광도의 합을 출력한다. 두 번째 줄에는 만들 수 있는 모든 사과나무의 에너지의 합을 출력한다. 답이 매우 클 수 있으므로 1,000,000,009로 나눈 나머지를 출력한다.
예제
6
0 1 3
1 2 2
2 3 5
1 4 6
4 5 7
4 6 4
1004
18026
출처
2017 FunctionCup 2번 문제
로그인해야 코드를 작성할 수 있어요.