Happy Life in University
Contest: Good Bye 2023
Difficulty rating: 2300
Tags: data structures, dfs and similar, greedy, trees

Egor and his friend Arseniy are finishing school this year and will soon enter university. And since they are very responsible guys, they have started preparing for admission already.

First of all, they decided to take care of where they will live for the long four years of study, and after visiting the university's website, they found out that the university dormitory can be represented as a root tree with $$$n$$$ vertices with the root at vertex $$$1$$$. In the tree, each vertex represents a recreation with some type of activity $$$a_i$$$. The friends need to choose $$$2$$$ recreations (not necessarily different) in which they will settle. The guys are convinced that the more the value of the following function $$$f(u, v) = diff(u, lca(u, v)) \cdot diff(v, lca(u, v))$$$, the more fun their life will be. Help Egor and Arseniy and find the maximum value of $$$f(u, v)$$$ among all pairs of recreations!

$$$^{\dagger} diff(u, v)$$$ — the number of different activities listed on the simple path from vertex $$$u$$$ to vertex $$$v$$$.

$$$^{\dagger} lca(u, v)$$$ — a vertex $$$p$$$ such that it is at the maximum distance from the root and is a parent of both vertex $$$u$$$ and vertex $$$v$$$.

Input format:
Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^{5}$$$).

The second line of each test case contains $$${n - 1}$$$ integers $$$p_2, p_3, \ldots,p_n$$$ ($$$1 \le p_i \le i - 1$$$), where $$$p_i$$$ — the parent of vertex $$$i$$$.

The third line of each test case contains $$${n}$$$ integers $$$a_1, a_2, \ldots,a_n$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ — the number of the activity located at vertex $$$i$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, output the maximum value of $$$f(u, v)$$$ for all pairs of recreations $$$(u, v)$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
Consider the fourth test case. The tree has the following structure:

Example input:
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

Example output:
2
9
9
12

Editorial:
Let's initiate a tree traversal from the first vertex, in which for each color on the path from the root to the current vertex, we will maintain the nearest vertex with that color, or note that it does not exist. This can be maintained using an array that is recalculated in $$$O(1)$$$. Now, for each vertex, let's remember all the vertices for which we are the nearest ancestor with the same color. Build a segment tree on the Euler tour that will support two operations — adding to a segment and finding the maximum. Let's start another traversal of the tree, and for each vertex, we will maintain the count of different colors on the path from it to the vertex we are currently traversing with depth-first search. It is then asserted that we need to add $$$1$$$ to the entire subtree of this vertex and subtract $$$1$$$ from the subtrees of all vertices for which we are the nearest ancestor with the same color. After that, we need to find the $$$2$$$ maximums among all the subtrees of the children and update the answer using them.