题目描述：

Alex is a professional computer game player.

These days, Alex is playing a war strategy game. The kingdoms in the world form a rooted tree. Alex's kingdom 1 is the root of the tree. With his great diplomacy and leadership, his kingdom becomes the greatest empire in the world. Now, it's time to conquer the world!

Alex has almost infinite armies, and all of them are located at 1 initially. Every week, he can command one of his armies to move one step to an adjacent kingdom. If an army reaches a kingdom, that kingdom will be captured by Alex instantly.

Alex would like to capture all the kingdoms as soon as possible. Can you help him?

题意：

每次可以从根节点派出一个军队，或者让已有军队走一格
军队移动到的点会被永久占领
求覆盖所有点的最少时间

题解：

首先：
1.达到叶子节点的话，那么路径上的点也会被占领，问题就变成到所有叶子节点的最短时间
2.第一步肯定是从根节点到叶子节点，为了让距离更短，我们要到深度最低的叶子节点
3.到达根叶子节点有两个办法，一个是从根节点出发到叶子节点，还一个办法是从旁边的叶子节点出发到另一个叶子节点
4.所以我们要统计两个值，一个是根节点到叶子节点的距离，一个是叶子节点彼此到达的距离，然后取最小
5.根节点到叶子节点的距离就是该点的深度。而叶子节点之间该按照什么顺序到达？
想想，我们从一个叶子节点A到另一个叶子节点B，肯定要先从A走到他俩的lca处，然后再走到B，就相当于A到lca这段距离走了两边（就是进出），而B只走一遍，如果是从A->B->C,除了C都走了两遍，为了让距离更短，我们应该让最长的走一遍，其余的走两遍。
对于每一个子树，最长链走一次，其余链走两次
所以对于每一个子树而言，我们需要将其按照最长链进行排序，从小到大
以上是思路，现在讲讲代码实现
两个dfs
dfs1是对每个点求深度，这是基本操作
同时排序，把所有出边按照最深叶子深度从小到大排序。精髓排序。
node有两个值，second指的是节点编号
first指的是对于一个树枝，叶子节点为1，从里往外依次+1
按照first排序后，第二次dfs就先遍历根节点
dfs2就是计算子底向上的最短距离，和深度取最小值
pair 默认对first升序，当first相同时对second升序；

7
1 2 3 4 4 5

图片说明
图片说明
最终贡献都在叶子节点上

代码：

#include<bits/stdc++.h>
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(int i=0;i<node[u].size();i++)
    {
        node[u][i].first=max(node[u][i].first,dfs1(node[u][i].second,dep+1));
    }
    printf("====未排序\n"); 
    for(int i=0;i<node[u].size();i++)
    {

        printf("node[%d][%d].first=%d\n",u,i,node[u][i].first);
        printf("node[%d][%d].second=%d\n",u,i,node[u][i].second);
    }
    sort(node[u].begin(),node[u].end());
    printf("====排序\n"); 
    for(int i=0;i<node[u].size();i++)
    {

        printf("node[%d][%d].first=%d\n",u,i,node[u][i].first);
        printf("node[%d][%d].second=%d\n",u,i,node[u][i].second);
    }

    return node[u].back().first+1;
}

int dfs2(int u,int dis)
{

    val[u]=dis;//dis储存的是到达当前点的最短距离 
    if(node[u].empty())
        return 1;
    int mmin=dis;//到当前节点的最近距离 
        for(int i=0;i<node[u].size();i++)
    {
        printf("node[%d][%d].second=%d\n",u,i,node[u][i].second);
        mmin=min(deep[u],dfs2(node[u][i].second,mmin+1));
    }
    return mmin+1;//返回值为自底向上的最短距离,
}

int main()
{
    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);
//        for(int u=1;u<=n;u++)
//        for(int i=0;i<node[u].size();i++)
//    {
//        
//    //    printf("node[%d][%d].first=%d\n",u,i,node[u][i].first);
//        printf("node[%d][%d].second=%d\n",u,i,node[u][i].second);
//    }
        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;
}
/*
1
6
1 2 3 4 4
*/