问题 E: Equivalence

You are given two trees �1,�2T1,T2, both with $n$ vertices. The lengths of edges of �1T1 are given. The length of each edge is non-negative.

A tree $T$ with $n$ vertices is good, if there is a way to assign each edge on �2T2 with a length which satisfies the following condition:

• For each pair $i,j$ satisfying $1\le i<j\le n$, the distances of $i$ and $j$ on $T$ and �2T2 are the same.

You can perform the following operation on �1T1: select an edge on �1T1 and replace its length with any non-negative integer.

Find the minimum number of operations to make �1T1 good.

The first line of input contains a single integer $T$ ($1\le T\le 8600$), denoting the number of test cases.

For each test case, the first line contains one integer $n$ (2≤�≤1062≤n≤106).

The second line contains $n-1$ integers �2,�3,⋯,��p2,p3,⋯,pn (1≤��≤�1≤pi≤n).

The third line contains $n-1$ integers ���2,���3,⋯,����val2,val3,⋯,valn (0≤����≤1090≤vali≤109).

These two lines denotes $n-1$ edges (�,��)(u,pu) with length ����valu on �1T1.

The fourth line contains $n-1$ integers �2′,�3′,⋯,��′p2′,p3′,⋯,pn′ (1≤��′≤�1≤pi′≤n), denoting $n-1$ edges (�,��′)(u,pu′) on �2T2.

It is guaranteed that ∑�≤1.1⋅106∑n≤1.1⋅106.

1
5
1 5 2 2 
0 2 3 1 
5 5 5 1 

1