题意： 每次可以从根节点派出一个军队，或者让已有军队走一格。 求覆盖所有点的最少时间。
思路： 题目可以转换为覆盖所有叶子，最后所有的军队都会停留在叶子上。 覆盖一个叶子，要么是从根节点派一个军队出来，要么是之前一个叶子的军队派过来。
所以对于每个叶子，我们只需要维护两个东西，一个是其深度——根节点派军队的花费；一个是之前某个有军队叶子到当前叶子的最小距离。
我们肯定不能对于之前所有叶子都判断一遍，所以我们需要找到一个合理的遍历顺序，使得只可能存在上一个叶子到当前叶子，或者根节点到当前叶子的情况。
一个直观的想法就是肯定是优先遍历深度较低的叶子，不过我们还得考虑叶子的相对位置关系，使得遍历的叶子尽量靠近。
对于本题，如果根节点下边很多条链，那么直接按照叶子深度从小到大遍历即可。 但如果子节点很多个分叉，则不能这样遍历。因为子树间的叶子遍历，是一个子树深度最深的叶子和一个子树深度最浅叶子遍历。
证明： 对于节点 x x x一个子树的叶子 a , b a,b a,b，另外一个子树的叶子 c , d c,d c,d，如图所示，满足 h 4 > h 3 h4>h3 h4>h3， h 6 > h 5 h6>h5 h6>h5。 同一个子树内叶子“通信”的方式肯定是按照深度从小到大，不需要管。
对于不同子树叶子的通信，我们肯定只需要考虑每个子树的最深叶子和最浅叶子：
所以对于下面的叶子有两种合并方式。
d d d与 a a a合并： h 6 + h 1 + h 2 + h 3 h6+h1+h2+h3 h6+h1+h2+h3 b b b与 c c c合并： h 4 + h 1 + h 2 + h 5 h4+h1+h2+h5 h4+h1+h2+h5其中 h 1 + h 2 h1+h2 h1+h2是所有子树间叶子合并的公有部分，唯一要考虑的部分就是叶子到 l c a lca lca的距离。所以叶子到 l c a lca lca距离越大，也就是深度越大，那么合并的花费越大，所以我们按照最深叶子排序，实际上最小化了子树间叶子合并的花费。
否则就可能出现下面这种情况：先遍历了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; }