|
||||||||||
EquivalenceTime Limit: 6000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 174 Accepted Submission(s): 64 Problem Description You are given two trees $T_1, T_2$, both with $n$ vertices. The lengths of edges of $T_1$ 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 $T_2$ 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 $T_2$ are the same. You can perform the following operation on $T_1$: select an edge on $T_1$ and replace its length with any **non-negative** integer. Find the minimum number of operations to make $T_1$ good. Input 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\le n\le 10^6$). The second line contains $n-1$ integers $p_2, p_3,\cdots, p_n$ ($1 \le p_i \le n$). The third line contains $n-1$ integers $val_2,val_3,\cdots, val_n$ ($0 \le val_i \le 10^9$). These two lines denotes $n-1$ edges $(u,p_u)$ with length $val_u$ on $T_1$. The fourth line contains $n-1$ integers $p'_2, p'_3,\cdots, p'_n$ ($1 \le p'_i \le n$), denoting $n-1$ edges $(u,p'_u)$ on $T_2$. It is guaranteed that $\sum n\le 1.1\cdot 10^6$. Output For each test case, the only line contains one integer denoting the answer. Sample Input
Sample Output
Source | ||||||||||
|