前言:感谢博主@crazy_fz 提供的思路。我借鉴的是他的思路，然后大概具体讲述一下大佬的思路吧。
原文链接：
题意：给定一颗以1为根的树，根节点处有无数个人，每一秒只能派一个人移动到他的相邻节点上，问最少需要多少秒才能使所有结点被访问过
解法: 我们分析一个树，发现如果只派出去一个士兵的话，那么实际上我们可以发现一个结论：除了子树上的最长链，其余的各个边都走了2次。那么在有且只有一个士兵的情况之下，最优(即最小步数)就是把这个最长链放到最后去走(这样就可以减少掉头回来的重复步数啦！)。那么在之前那个博主所提到的“把子树按高度从小到大排序”其实就是这个道理：为了避免过度冗余走重复的路径，我们按照子树的大小升序排列，就可以最优化走的步骤。但是问题出来了：什么时候发兵，什么时候沿用左边那棵树的士兵呢？这个时候我们可以比较一下该点t到左边那棵树v的最深点的距离(因为之前说过从小到大排列子树了)与其到根节点root的距离，如果说从那个最深点到该节点的距离＞root到该节点的距离，那么最优的方法应该是从root点派遣新的士兵，反之沿用左边树上的士兵。这就是整个题的贪心过程。然后最后答案统计的时候，其实只需要把到每个叶子结点的时间求个sum就行。(因为全程只能动1个士兵，而不是多个士兵同时可以动1格，搞清题意)。
难点分析：因为我自己写链式前向星写多了，对于子树排序其实建图更适用于用vector来建，因为这样可以对子节点的顺序进行排序操作。而链式前向星不具备这个特性。此外回溯的时候的dfs写法也值得深思。
然后最近补题的可以问教练要邀请码然后去PTA上建重现赛(有效时长是4天)
AC代码：
#include
#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;//代码效果参考：http://www.lyjsj.net.cn/wx/art_22722.html
i>=a;i--)#define endl '\n'
#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
int,intvec【maxn】;//深度,儿子
int getdp(int x){
if(!vec【x】.size()) return 1;
for(int i=0;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\n",cas,ans);
}
return 0;
}
/
1
11
1 2 3 4 4 4 7 4 9 9
/
View Code
前ICPC算法竞赛退役选手|现摸鱼ing
