题目描述

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

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

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

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

输入格式

第一行输入一个正整数 $T$ ($1≤T≤3$) 代表数据组数。

对于每组数据：

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

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

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

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

输出格式

对于每个测试样例输出一行一个正整数代表答案。

输入样例

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

提示

一种最优的旅行方案为：

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

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

价值总和为 $13$。