题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6867
题意：给定一棵树，随意连一条边构成基环树，求怎样构造使得相互连通的点对数量最大。
思路：最优解一定是某个叶子结点连向根节点，先dfs一遍预处理出每个点子节点个数，再dfs一次，每次比较取最大值。
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N =5e5+5;
vector<int>e[N];
ll v[N];</int>

void dfs(int x)
{
v[x] = 1;
for(int i = 0; i < e[x].size(); i++)
{
dfs(e[x][i]);
v[x] = v[x] + v[e[x][i]];
}
}

ll ans = 0;
void DFS(int x,ll temp)
{
ans = max(ans, temp + v[1] - v[x]);
for(int i = 0; i < e[x].size(); i++)
{
DFS(e[x][i], temp + v[1] - v[x]);
}
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T; cin >> T;
while(T--)
{
int n; cin >> n;
for(int i = 0; i <= n; i++) e[i].clear();
for(int i = 2; i <= n; i++)
{
int p; cin >> p;
e[p].push_back(i);
}
dfs(1);
ans = 0;
for(int i = 1; i <= n; i++) ans += v[i];
DFS(1, ans);
cout<< ans <<endl;
}
return 0;
}