Snakes capturing the Mongoose Cities

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
The Mongoose Land consists of N cities and they are connected by N  1 bidirectional roads in such a manner that you can travel from one city to another city in exactly one path. In other words, the map looks like a tree. The cities are numbered from 1 to N.
King Cobra has decided that he wants to eliminate the mongooses, and is hence preparing to wage a war. The snakes have recently procured airplanes, and thus they can parachute their soldiers onto some of the Mongoose Land cities. Suppose on Day 0, these soldiers are parachuted. You know that to capture City i, you need to parachute in P_{i} soldiers. By end of Day 0, they would have captured their respective cities.
Each city depends on its neighbors for some of its supplies, and so, if a certain number of its neighbors are captured, then this city will fall as well. In particular, for every City i, you know that if City i was uncaptured on Day d, and at least C_{i} of its neighbors are captured on Day d, then this city will be captured on Day d+1, where d ≥ 0. A city which has been captured will forever remain captured.
King Cobra doesn't mind waiting for however long it takes to capture the entire Mongoose kingdom, but he wants to do it with the least number of soldiers. Help him find the least number of soldiers he should send so that the entire Mongoose kingdom can be captured eventually.
Formally, you need to find a subset of cities, S, such that the sum of P_{i} over these cities is minimized, and the entire kingdom will be captured eventually, if soldiers are parachuted into exactly these cities. You need to output this minimum sum.
Input
 The first line contains a single integer, T, denoting the number of testcases. The description of each testcase follows.
 The first line of each testcase contains a single integer, N, the number of cities in Mongoose Land,
 The ith of the next N  1 lines contain two integers each, u_{i} and v_{i}, which denote that there is an edge between Cities u_{i} and v_{i}.
 The next line contains N integers, P_{1}, P_{2}, ..., P_{N}. P_{i} denotes the number of soldiers which have to parachuted in, so as to capture City i on Day 0.
 The next line contains N integers, C_{1}, C_{2}, ..., C_{N}. C_{i} denotes the number of neighbors of City i that have to be captured for City i to be captured on the next day.
Output
 For each testcase, output a single integer which is the minimum total number of soldiers who have to be parachuted in, on Day 0.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N ≤ 5 * 10^{4}
 1 ≤ u_{i}, v_{i} ≤ N
 1 ≤ P_{i} ≤ 10^{9}
 1 ≤ C_{i} ≤ degree of City i
Example
Input: 1 8 1 2 1 3 4 2 6 5 2 5 7 5 5 8 2 8 10 5 200 4 100 1 2 1 1 1 3 1 1 1 Output: 7
Explanation
One of the optimal solutions is to parachute into Cities 1, 6 and 8 on Day 0. So the total number of soldiers needed = P_{1} + P_{6} + P_{8} = 2 + 4 + 1 = 7.
Now, we will show that this is indeed a valid solution. For that, we need to show that eventually all the cities will be captured. We will show the cities captured on every day in sequence:
 Day 0: The cities captured are the ones parachuted into, and they are {1, 6, 8}.
 Day 1: City 2 has one of its neighbors (City 1) captured. And since C_{2} = 1, this is enough for City 2 to be captured. Similarly, since C_{3} = 1, and City 1 is a neighbor of City 3, City 3 is also captured. So, cities captured on day 1 = {1, 2, 3, 6, 8}.
 Day 2: City 4 has C_{4} = 1, and one of its neighbors is captured (City 2). Hence it is captured now. City 5 has C_{5} = 3, and three of its neighbors, Cities 2, 6 and 8, have been captured. Hence it is also captured. Therefore the cities captured at the end of Day 2 are {1, 2, 3, 4, 5, 6, 8}.
 Day 3: City 7 has C_{7} = 1 and since City 5 has been captured, it is also captured now. So, by the end of Day 3, all 8 cities have been captured.
This cannot be achieved with fewer soldiers, and hence the answer is 7.
Author:  admin3 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/CAPTCITI 
Tags  admin3, medium, snckpb17, sorting, treedp 
Date Added:  30052017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 