旅行

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

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

Sample Input

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

Sample Output

13

Hint

一种最优的旅行方案为： 旅行路线1：$4\to 2\to 5$ ，价值为 $9$。 旅行路线2：$1\to 3\to 7$，价值为 $4$。 价值总和为 $13$。

Source

2024“钉耙编程”中国大学生算法设计超级联赛（3）