F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Tree

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1153    Accepted Submission(s): 446


Problem Description
You are given a tree consisting of $n$ vertices numbered $1$ to $n$ rooted at node $1$. The parent of the $i$-th vertices is $p_i$. You can move from a vertex to any of its children. What's more, you can add one directed edge between any two different vertices, and you can move through this edge too. You need to maximize the number of pairs $(x,y)$ such that $x$ can move to $y$ through the edges after adding the edge. Note that $x$ can also move to $x$.
 

Input
The first line contains one integer $T$ $(1\leq T\leq 100000)$ the number of test cases.

The first line of each test case contains only one integer $n(1\leq n\leq 5\times 10^5)$ the number of vertices in the tree.

The second line of each test case contains $n-1$ integers $p_2,p_3,\dots,p_n (1\leq p_i<i)$ the parent of each non-root node.

The sum of $n$ over all test cases does not exceed $10^6$.
 

Output
Print $T$ integers for each test case output the maximum number of pairs $(x,y)$ that vertices $x$ can move to $y$ after adding one edge.
 

Sample Input
2 5 1 1 2 2 6 1 2 3 1 3
 

Sample Output
17 26
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2023 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2023-05-31 23:47:09, Gzip enabled