Monster Hunter
시간 제한4초메모리 제한512 MB
1번을 루트로 하는 트리에서 각 정점에 소모 HP와 회복 HP가 주어질 때, 모든 몬스터를 처치하는 동안 HP가 음수가 되지 않도록 하는 최소 초기 HP를 구한다.
문제
리틀 Q는 게임 "Monster Hunter"에서 무서운 몬스터와 싸우고 있다. 전장은 1, 2, ..., n으로 번호가 붙은 n개의 교차점으로 이루어져 있고, n - 1개의 양방향 도로가 트리처럼 교차점들을 연결한다. 리틀 Q는 현재 교차점 1에 있고 X의 체력(HP)을 가지고 있다.
교차점 1을 제외한 각 교차점에는 몬스터가 있다. 리틀 Q가 k번째 교차점에 처음으로 이동하면, 그 교차점의 몬스터와 싸워야 한다. 싸우는 동안 그는 a_i의 HP를 잃는다. 그리고 마침내 몬스터를 이기면 b_i의 HP를 받는다. HP가 음수가 되면(< 0) 게임이 종료되므로, 절대 그렇게 되어서는 안 된다. 리틀 Q가 같은 교차점을 두 번 이상 방문하면, 싸움은 첫 방문에서만 일어난다. 몬스터는 여분의 목숨이 없기 때문이다.
모든 몬스터를 처치하면 리틀 Q는 게임에서 이긴다. 승리로 이끌 수 있는 최소 초기 HP를 계산하는 프로그램을 작성하시오.
입력
입력의 첫 번째 줄에는 정수 T (1 ≤ T ≤ 2000)가 주어지며, 이는 테스트 케이스의 수를 나타낸다.
각 테스트 케이스에서 첫 번째 줄에는 정수 n (2 ≤ n ≤ 100 000)이 주어지며, 이는 교차점의 수를 나타낸다.
다음 n - 1개의 줄 각각에는 두 정수 a_i와 b_i (0 ≤ a_i, b_i ≤ 10^9)가 주어지며, 이는 교차점 2, 3, ..., n에 있는 몬스터를 나타낸다.
다음 n - 1개의 줄 각각에는 두 정수 u와 v (1 ≤ u, v ≤ n, u ≠ v)가 주어지며, 이는 교차점 u와 교차점 v 사이의 양방향 도로를 나타낸다. 도로가 트리를 이룸이 보장된다.
모든 n의 합은 10^6 이하임이 보장된다.
출력
각 테스트 케이스에 대해, 게임에서 이기는 데 필요한 최소 초기 HP를 나타내는 정수를 한 줄에 출력한다.