前言:感谢博主@crazy_fz 提供的思路。我借鉴的是他的思路，然后大概具体讲述一下大佬的思路吧。
原文链接：https://www.cnblogs.com/crazyfz/p/13838422.html
题意：给定一颗以1为根的树，根节点处有无数个人，每一秒只能派一个人移动到他的相邻节点上，问最少需要多少秒才能使所有结点被访问过
解法: 我们分析一个树，发现如果只派出去一个士兵的话，那么实际上我们可以发现一个结论：除了子树上的最长链，其余的各个边都走了2次。那么在有且只有一个士兵的情况之下，最优(即最小步数)就是把这个最长链放到最后去走(这样就可以减少掉头回来的重复步数啦！)。那么在之前那个博主所提到的“把子树按高度从小到大排序”其实就是这个道理：为了避免过度冗余走重复的路径，我们按照子树的大小升序排列，就可以最优化走的步骤。但是问题出来了：什么时候发兵，什么时候沿用左边那棵树的士兵呢？这个时候我们可以比较一下该点t到左边那棵树v的最深点的距离(因为之前说过从小到大排列子树了)与其到根节点root的距离，如果说从那个最深点到该节点的距离＞root到该节点的距离，那么最优的方法应该是从root点派遣新的士兵，反之沿用左边树上的士兵。这就是整个题的贪心过程。然后最后答案统计的时候，其实只需要把到每个叶子结点的时间求个sum就行。(因为全程只能动1个士兵，而不是多个士兵同时可以动1格，搞清题意)。
难点分析：因为我自己写链式前向星写多了，对于子树排序其实建图更适用于用vector来建，因为这样可以对子节点的顺序进行排序操作。而链式前向星不具备这个特性。此外回溯的时候的dfs写法也值得深思。
然后最近补题的可以问教练要邀请码然后去PTA上建重现赛(有效时长是4天)
AC代码：
#include<bits/stdc++.h> #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ' ' #define eps 0.000000001 #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=1e6+5; vector<pair<int,int> >vec[maxn];//深度,儿子 int getdp(int x){ if(!vec[x].size()) return 1; for(int i=0;i<vec[x].size();i++){ vec[x][i].first=getdp(vec[x][i].second); } sort(vec[x].begin(),vec[x].end()); return vec[x].back().first+1; }//统计每个点的高度并且按照升序排序 int val[maxn];//从上一个叶子点(或根节点)到该点的最小步数 int dfs(int x,int d,int v){//d统计深度，v代表到该点最小步数 val[x]=v; if(!vec[x].size()) return 1;//回溯过程 int now=v; for(auto it:vec[x]){ now=min(d,dfs(it.second,d+1,now+1)); //不断从左树往右树更新now即耗时 } return now+1; } int main(){ int T;scanf("%d",&T); for(int cas=1;cas<=T;cas++){ int n;scanf("%d",&n); rep(i,1,n) vec[i].clear(); rep(i,2,n){ int x;scanf("%d",&x); vec[x].push_back({0,i}); } getdp(1); dfs(1,0,0); ll ans=0; rep(i,1,n){ if(!vec[i].size()) ans+=val[i];//把叶子结点的贡献全部算上 } printf("Case #%d: %lld ",cas,ans); } return 0; } /* 1 11 1 2 3 4 4 4 7 4 9 9 */