F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Problem H. Monster Hunter

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 2263    Accepted Submission(s): 548


Problem Description
Little Q is fighting against scary monsters in the game ``Monster Hunter''. The battlefield consists of $n$ intersections, labeled by $1,2,...,n$, connected by $n-1$ bidirectional roads. Little Q is now at the $1$-th intersection, with $X$ units of health point(HP).
There is a monster at each intersection except $1$. When Little Q moves to the $k$-th intersection, he must battle with the monster at the $k$-th intersection. During the battle, he will lose $a_i$ units of HP. And when he finally beats the monster, he will be awarded $b_i$ units of HP. Note that when HP becomes negative($<0$), the game will over, so never let this happen. There is no need to have a battle at the same intersection twice because monsters do not have extra life.
When all monsters are cleared, Little Q will win the game. Please write a program to compute the minimum initial HP that can lead to victory.
 

Input
The first line of the input contains an integer $T(1\leq T\leq2000)$, denoting the number of test cases.
In each test case, there is one integer $n(2\leq n\leq 100000)$ in the first line, denoting the number of intersections.
For the next $n-1$ lines, each line contains two integers $a_i,b_i(0\leq a_i,b_i\leq 10^9)$, describing monsters at the $2,3,...,n$-th intersection.
For the next $n-1$ lines, each line contains two integers $u$ and $v$, denoting a bidirectional road between the $u$-th intersection and the $v$-th intersection.
It is guaranteed that $\sum n\leq 10^6$.
 

Output
For each test case, print a single line containing an integer, denoting the minimum initial HP.
 

Sample Input
1 4 2 6 5 4 6 2 1 2 2 3 3 4
 

Sample Output
3
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-28 19:33:46, Gzip enabled