题目描述

Egor 和他的朋友 Arseniy 今年即将从学校毕业，很快就要进入大学。由于他们是非常负责的人，所以他们已经开始为入学做准备了。

首先，他们决定先考虑在漫长的四年学习生活中住在哪里。在访问大学网站之后，他们发现大学宿舍可以表示为一棵包含 $n$ 个顶点、根为顶点 $1$ 的有根树。在这棵树中，每个顶点表示一个休闲场所，其中有某种类型的活动 $a_i$ 。这两位朋友需要选择 $2$ 个休闲场所（不一定不同）作为他们将要安顿的地方。他们坚信，下面这个函数 $f(u, v) = diff(u, lca(u, v)) \cdot diff(v, lca(u, v))$ 的值越大，他们的生活就会越有趣。请帮助 Egor 和 Arseniy，找出所有休闲场所对中 $f(u, v)$ 的最大值！

$^{\dagger} diff(u, v)$ — 从顶点 $u$ 到顶点 $v$ 的简单路径上出现的不同活动数量。

$^{\dagger} lca(u, v)$ — 一个顶点 $p$ ，它距离根最远，并且同时是顶点 $u$ 和顶点 $v$ 的祖先。

输入格式

每个测试包含若干个测试用例。第一行包含一个整数 $t$（ $1 \le t \le 10^5$ ）— 测试用例的数量。接下来给出各个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（ $1 \le n \le 3 \cdot 10^{5}$ ）。

每个测试用例的第二行包含 ${n - 1}$ 个整数 $p_2, p_3, \ldots,p_n$（ $1 \le p_i \le i - 1$ ），其中 $p_i$ — 顶点 $i$ 的父节点。

每个测试用例的第三行包含 ${n}$ 个整数 $a_1, a_2, \ldots,a_n$（ $1 \le a_i \le n$ ），其中 $a_i$ — 位于顶点 $i$ 的活动编号。

保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$ 。

输出格式

对于每个测试用例，输出所有休闲场所对 $(u, v)$ 中 $f(u, v)$ 的最大值。

4
2
1
1 2
7
1 1 2 2 3 3
6 5 2 3 6 5 6
13
1 1 1 2 2 2 3 3 4 5 6 6
2 2 2 1 4 9 7 2 5 2 1 11 2
12
1 1 1 2 2 3 4 4 7 7 6
11 2 1 11 12 8 5 8 8 5 11 7

2
9
9
12

提示

考虑第四个测试用例。这棵树具有如下结构：

所有休闲场所都被染上了颜色。相同的颜色表示这些休闲场所中的活动相同。考虑顶点对 $(11, 12)$ ，$lca(11, 12) = 1$ 。写出从 $11$ 到 $1$ 的路径上的所有活动 — $[11, 5, 1, 11]$ ，其中有 $3$ 种不同的活动，因此 $diff(11, 1) = 3$ 。再写出从 $12$ 到 $1$ 的路径上的所有活动 — $[7, 8, 2, 11]$ ，其中有 $4$ 种不同的活动，因此 $diff(12, 1) = 4$ 。我们得到 $f(11, 12) = diff(12, 1) \cdot diff(11, 1) = 4 \cdot 3 = 12$ ，这就是这棵树的答案。可以证明，不可能得到更好的答案。