题意：
每次可以从根节点派出一个军队，或者让已有军队走一格。
求覆盖所有点的最少时间。
思路：
题目可以转换为覆盖所有叶子，最后所有的军队都会停留在叶子上。
覆盖一个叶子，要么是从根节点派一个军队出来，要么是之前一个叶子的军队派过来。
所以对于每个叶子，我们只需要维护两个东西，一个是其深度——根节点派军队的花费；一个是之前某个有军队叶子到当前叶子的最小距离。
我们肯定不能对于之前所有叶子都判断一遍，所以我们需要找到一个合理的遍历顺序，使得只可能存在上一个叶子到当前叶子，或者根节点到当前叶子的情况。
一个直观的想法就是肯定是优先遍历深度较低的叶子，不过我们还得考虑叶子的相对位置关系，使得遍历的叶子尽量靠近。
对于本题，如果根节点下边很多条链，那么直接按照叶子深度从小到大遍历即可。
但如果子节点很多个分叉，则不能这样遍历。因为子树间的叶子遍历，是一个子树深度最深的叶子和一个子树深度最浅叶子遍历。
否则就可能出现下面这种情况：先遍历了9，在遍历12。
所以遍历的顺序是：将每个节点保存为其子树所有叶子的最大深度，然后按从小到大顺序遍历。对每个叶子统计答案。
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>using namespace std;
typedef long long ll;const int maxn = 1e6 + 7;int ye[maxn];
vector<int>G[maxn];
ll ans;int cmp(int x,int y) {
return ye[x] < ye[y];
}void dfs1(int x) {
if(G[x].size() == 0) ye[x] = 1;for(int i = 0 ;i < G[x].size();i++) {
int v = G[x][i];dfs1(v);ye[x] = max(ye[x],ye[v] + 1);}sort(G[x].begin(),G[x].end(),cmp);
}void dfs2(int x,int dep,int v) {
//dep代表这个点的深度，v代表离这个子树最近的叶子if(G[x].size() == 0) {
ans += v;ye[x] = 1;return;}int t = v;for(int i = 0;i < G[x].size();i++) {
int y = G[x][i];dfs2(y,dep + 1,t + 1);t = min(dep,ye[y]);}ye[x] = t + 1;
}int main() {
int T;scanf("%d",&T);int kase = 0;while(T--) {
int n;scanf("%d",&n);for(int i = 1;i <= n;i++) {
G[i].clear();ye[i] = 0;}for(int i = 2;i <= n;i++) {
int x;scanf("%d",&x);G[x].push_back(i);}dfs1(1);ans = 0;dfs2(1,0,0);printf("Case #%d: %lld\n",++kase,ans);}return 0;
}