提示: 欢迎访问OurACM平台。
Problem 2157 ProgramCaicai's Trees

Accept: 62    Submit: 155
Time Limit: 15000 mSec    Memory Limit : 32768 KB

Problem Description

Given a Tree of N nodes.

Each node has exactly two labels.(0 and 1).

You must choose which label to assign to give the minimum cost.

The Cost is the sum of two parts:

1. For each node their is a cost assigned to the node for a given label.

2. For each pairs of Node connected their is a cost assigned to it according to it's labels.

Input

In the first line, there are a number T(<=50) denotes the number of test cases.

In the second line, there are a number N(<=200000) denoting the number of Nodes.

In the third line, N numbers denoting the cost for each node assigned to label 0.

In the fourth line, N numbers denoting the cost for each node assigned to label 1.

In the next n-1 lines. each line containing six numbers P Q A B C D, P Q indicates there is a edge between P and Q , and A B C D are cost assigned to pairs of nodes which label is 00 01 10 11 accordingly.

The Tree root is always Node 1

Every cost is between 0 and 100

only 2 big cases

Output

The Minimum cost of the given tree.(A Integer)

Sample Input

1 4 3 1 1 3 4 0 0 4 1 2 0 1 1 0 2 3 0 1 1 0 2 4 0 1 1 0

Sample Output

8

Submit  Back  Status  Discuss