题目大意：给出一棵 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; }
