宝石计划

众所周知，冲神和昊神是非常要好的♂好朋友♂，一起学习一起打acm住一个寝室并且一起保研。他们两个都是宝石收藏家，但是冲神喜欢红宝石，昊神喜欢绿玛瑙。
为了获取梦寐以求的宝石们，他们一起来到了神奇的宝石王国。这里一共有n个宝石矿洞，并由n-1条路将所有矿洞相连。每个矿洞最多只能走一次。
第i个矿洞中有红宝石ai个和绿玛瑙bi个，冲神和昊神会分别拿走所有自己喜欢的宝石，并且希望自己和对方宝石个数的差值尽可能大。由冲神选择起点，他们会轮流选择下一个地点，直到无路可走为止。
他们俩都是绝顶聪明的程序员，每次都会做出最优的选择（使最终自己和对方宝石个数差值最大）。请你计算出最终冲神的宝石比昊神的宝石多多少个。

第一行一个整数n，表示矿洞个数。（1≤n≤1e5）
接下来一行n个整数，第i个整数ai表示第i个矿洞中有ai个红宝石。（0≤ai≤1e6）
接下来一行n个整数，第i个整数bi表示第i个矿洞中有bi个绿玛瑙。（0≤bi≤1e6）
接下来n-1行，第j行两个整数uj，vj，表示第uj和第vj个矿洞间有一条路。（1≤uj≤n， 1≤vj≤n）

一个整数，表示冲神的宝石比昊神的宝石多多少个。

Sample1:
3
1 1 1
0 2 3
1 2
1 3

Sample2:
7
243979 530822 510330 373112 6626 752040 941919
220449 45491 456495 567040 622771 279803 60441
4 5
1 3
1 2
4 1
6 1
4 7

Sample1:
-1

Sample2:
981098