题目大意：给出一棵 n 个节点的有根树，点 1 为根节点，现在在根节点有无穷多个士兵，每一秒可以控制任意一个士兵向任意一个单位移动一步，士兵移动到的点会被永久占领，现在问最少需要经过多少秒，才能将所有的点都占领
题目分析：首先不难看出的两个小结论是：
- 如果所有的叶子节点都被占领，那么沿途的所有点也会被占领，所以问题转换为了到每个叶子节点的最短时间
- 第一步肯定是需要从根节点到其中一个叶子节点的，贪心去想，到深度最低的那个叶子节点一定是最优的
树形dp维护一下从根节点过来更优还是从相邻的叶子结点更优，然后更新答案即可，这里参考了网上的解法，形式参数维护一个变量表示到达当前节点时的最短距离，递归的返回值是自底向上的最短距离，也就是从相邻的叶子节点过来的距离，这个距离和深度取个最小值就是答案了
最后还有一点需要贪心去考虑，感觉这个就是本题的难点了，假设只有一个士兵，从根节点出发若想遍历整棵树的话，最短的路线一定是：对于每个子树而言，最长的链只遍历一次，其余的链都会被遍历两次
基于此，对于每个子树而言，我们只需要将其按照 最长链 进行排序即可，因为最后去遍历的话一定只需要走一遍
代码：
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;vector<pair<int,int>>node[N];int deep[N],val[N];int dfs1(int u,int dep)
{if(node[u].empty())return 1;deep[u]=dep;for(auto &it:node[u]){int v=it.second;it.first=max(it.first,dfs1(v,dep+1));}sort(node[u].begin(),node[u].end());return node[u].back().first+1;
}int dfs2(int u,int dis)//返回值为自底向上的最短距离,dis储存的是到达当前点的最短距离
{val[u]=dis;if(node[u].empty())return 1;int mmin=dis;//到当前节点的最近距离 for(auto it:node[u]){int v=it.second;mmin=min(deep[u],dfs2(v,mmin+1));}return mmin+1;
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int w;cin>>w;int kase=0;while(w--){int n;scanf("%d",&n);for(int i=1;i<=n;i++)node[i].clear();for(int i=2;i<=n;i++){int fa;scanf("%d",&fa);node[fa].push_back(make_pair(0,i));}dfs1(1,0);dfs2(1,0);LL ans=0;for(int i=1;i<=n;i++)if(node[i].empty())ans+=val[i];printf("Case #%d: %lld\n",++kase,ans);}return 0;
}