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

Acesrc and Travel

Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 2096    Accepted Submission(s): 538


Problem Description
Acesrc is a famous tourist at Nanjing University second to none. During this summer holiday, he, along with Zhang and Liu, is going to travel to Hong Kong. There are $n$ spots in Hong Kong, and $n - 1$ bidirectional sightseeing bus routes connecting these spots. They decide to visit some spots by bus.

However, Zhang and Liu have different preferences for these spots. They respectively set a satisfactory value for each spot. If they visit the $i$th spot, Zhang will obtain satisfactory value $a_i$, and Liu will obtain $b_i$. Starting with Zhang, they alternately decide the next spot to visit for the sake of fairness. There must be a bus route between the current spot and the next spot to visit. Moreover, they would never like to visit a spot twice. If anyone can't find such a next spot to visit, they have no choice but to end this travel.

Zhang and Liu are both super smart competitive programmers. Either want to maximize the difference between his total satisfactory value and the other's. Now Acesrc wonders, if they both choose optimally, what is the difference between total satisfactory values of Zhang and Liu?
 

Input
The first line of input consists of a single integer $T$ $(1 \leq T \leq 30)$, denoting the number of test cases.

For each test case, the first line contains a single integer $n$ $(1 \leq n \leq 10^5)$, denoting the number of spots. Each of the next two lines contains $n$ integers, $a_1, a_2, \cdots, a_n$ and $b_1, b_2, \cdots, b_n$ $(0 \leq a_i, b_i \leq 10^9)$, denoting the
satisfactory value of Zhang and Liu for every spot, respectively. Each of the last $n - 1$ lines contains two integers $x, y$ $(1 \leq x, y \leq n, x \neq y)$, denoting a bus route between the $x$th spot and the $y$th spot. It is reachable from any spot to any other spot through these bus routes.

It is guaranteed that the sum of $n$ does not exceed $5.01 \times 10^5$.
 

Output
For each test case, print a single integer in one line, the difference of total satisfactory values if they both choose optimally.
 

Sample Input
1 3 1 1 1 0 2 3 1 2 1 3
 

Sample Output
-1
 

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-12-11 19:55:33, Gzip enabled