该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Description

有一棵 $n$ 个结点的无根树，每个结点都有对应的类型 $c_i$ 和权重 $w_i$ ，你需要在这棵树上规划若干次旅行。

对于一次旅行，你将从一个树上的一个结点出发，沿着树上的边进行旅行，最终到达另一个和起点类型相同的结点。

你会进行很多次旅行，但你希望对于每个结点，在所有旅行路线中最多只会经过一次。

一次旅行的价值是起始点和终止点的权重和，你需要规划旅行的方案使得旅行的总权重和最大。

Input

第一行输入一个正整数 $t\ (1\le t\le 3)$ 代表数据组数。

对于每组数据：

第一行输入一个正整数 $n\ (1\le n \le 2\times 10^5)$，代表树的点数。

第二行输入 $n$ 个正整数 $c_i\ (1\le c_i \le n)$ ，代表每个结点的类型。

第三行输入 $n$ 个正整数 $w_i\ (1\le w_i \le n)$ ，代表每个结点的权重。

接下来 $n-1$ 行每行两个正整数 $u_i,v_i\ (1\le u_i,v_i\le n,u_i\not=v_i)$ ,代表树上一条边，输入保证是一棵树。

Output

输出一行一个正整数代表答案。

1
7
3 1 1 2 2 2 3
2 4 1 5 4 6 2
1 2
1 3
2 4 
2 5
3 6 
3 7

13

Hint

一种最优的旅行方案为：

旅行路线1：$4\to 2\to 5$ ，价值为 $9$。

旅行路线2：$1\to 3\to 7$，价值为 $4$。

价值总和为 $13$。