L. Easy Tree Problem
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Thomas has set an easy tree problem! I can even tell you what it is:

There is a tree with $$$n$$$ nodes rooted at node $$$1$$$, each initially painted with color $$$a_i$$$. However, this color scheme is extremely ugly, and Thomas wants to paint it to make it beautiful instead. He wants each node to be painted with color $$$b_i$$$ in the end. However, this is a tree, so the paint will trickle down from a certain node, painting the entire subtree. It will cost $$$c_i$$$ dollars for Thomas to paint node $$$i$$$ and its entire subtree any color. Whenever Thomas paints a node, it will override any preexisting painted nodes in its subtree - the color of a node is the color of the last operation applied to it (or any of its ancestors). What is the minimum number of dollars Thomas needs to spend to paint the entire tree the colors that he wants?

I actually have been informed that I understood the problem wrong and created a new problem, so I am stuck preparing it instead. However, this is too hard for me to solve and my stamina is capping, so instead you will solve this problem for me!

As the input is extremely large, it is advised to use a form of fast input and output.

Input

The first line of the input will contain one integer $$$t$$$, the number of test cases.

Each test case will consist of $$$5$$$ lines.

The first line contains integer $$$n$$$ $$$(1\leq n\leq 200000)$$$. It is guaranteed that the sum of $$$n$$$ over all multitests is less than or equal to $$$2.5\cdot 10^6$$$.

The second line contains $$$n-1$$$ integers, with the $$$i$$$-th integer representing the parent of the $$$i+1$$$-th node of the tree.

The third line contains $$$n$$$ integers, with the $$$i$$$-th integer representing $$$c_i$$$ $$$(1\leq c_i\leq 10^9)$$$.

The fourth line contains $$$n$$$ integers, with the $$$i$$$-th integer representing $$$a_i$$$ $$$(1\leq a_i\leq 10^6)$$$.

The fifth line contains $$$n$$$ integers, with the $$$i$$$-th integer representing $$$b_i$$$ $$$(1\leq b_i\leq 10^6)$$$.

Test cases are enumerated from $$$1$$$ to $$$20$$$. Note that the data will not include samples.

Tests $$$1-5$$$: $$$t\leq 1000$$$, $$$n\leq 12$$$

Tests $$$6-20$$$: No additional restrictions

Output

For each test case on its own line, output one integer representing the answer for that test case. The answer may not fit in a $$$32$$$ bit integer.

Examples
Input
3
5
1 1 2 4
1 3 2 2 2
2 2 1 3 4
2 4 1 2 1
5
1 4 5 1
2 2 1 0 1
1 4 1 1 4
1 3 1 5 5
5
3 4 1 1
3 4 3 3 0
3 3 2 2 5
3 4 2 2 1
Output
7
4
4
Input
1
10
1 2 2 4 5 3 6 3 7
4 2 2 2 4 3 2 1 1 4
2 1 1 1 3 2 1 3 2 4
2 3 3 4 3 3 2 5 4 1
Output
16
Note

In the first multitest in the first sample, the most optimal sequence of operations is painting node $$$1$$$ color $$$2$$$ with cost $$$1$$$ and then painting node $$$2$$$ color $$$1$$$ with cost $$$1$$$. After painting node $$$1$$$ color $$$2$$$, node $$$1$$$ and node $$$2$$$ are both color $$$2$$$, as node $$$2$$$ is in the subtree of node $$$1$$$. Then, painting node $$$2$$$ color one ends in the desired color configuration.

In the second multitest in the first sample, the most optimal sequence of operations is painting node $$$2$$$ with color $$$4$$$, then painting node $$$4$$$ with color $$$2$$$, and then painting node $$$5$$$ with color $$$1$$$, with costs $$$3$$$, $$$2$$$, and $$$2$$$ for a total of $$$7$$$.

 —

Problem Idea: hyforces

Problem Preparation: hyforces

Occurrence: Novice $$$12$$$, Advanced $$$6$$$