思路
要么是让人走到叶子结点，再折返到岔口走下一个叶子结点。 要么是折返的花费高于从根派一个新的人过来，走到其他的叶子结点。
那就要获得树的深度信息，通过深度信息获取结点到根的距离以及各叶子结点到岔口的距离。
并且由于我们肯定是优先走深度小的叶子结点，再走深度深的叶子结点，所以需要对每个结点，都对以它为根节点的子树按照各分支的最大深度排序。
排序后树的每个分支都是左低又高，从左往右深搜并更新答案即可。
代码
#include <bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const int maxn
= 1e6 + 10;
vector
<int> vec
[maxn
];
int deep
[maxn
], max_deep
[maxn
], pre
[maxn
];
int ans
;
void dfs(int u
, int pre
){
deep
[u
] = deep
[pre
] + 1;
max_deep
[u
] = deep
[u
];
for(int i
= 0; i
< vec
[u
].size(); i
++){
int v
= vec
[u
][i
];
if(v
!= pre
){
dfs(v
, u
);
max_deep
[u
] = max(max_deep
[u
], max_deep
[v
]);
}
}
}
void dfs2(int u
, int fa
){
pre
[u
] = u
;
for(int i
= 0; i
< vec
[u
].size(); i
++){
int v
= vec
[u
][i
];
if(v
!= fa
){
ans
+= min(deep
[u
], deep
[pre
[u
]] - deep
[u
] + 1);
dfs2(v
, u
);
pre
[u
] = pre
[v
];
}
}
}
bool cmp(int x
, int y
){
return max_deep
[x
] < max_deep
[y
];
}
int main(){
int t
, Case
= 1; scanf("%d", &t
);
while(t
--){
int n
; scanf("%d", &n
);
ans
= 0;
for(int i
= 2, x
; i
<= n
; i
++){
scanf("%d", &x
);
vec
[i
].push_back(x
), vec
[x
].push_back(i
);
}
dfs(1, 0);
for(int i
= 1; i
<= n
; i
++){
sort(vec
[i
].begin(), vec
[i
].end(), cmp
);
}
dfs2(1, 0);
printf("Case #%d: %d\n", Case
++, ans
);
for(int i
= 1; i
<= n
; i
++)
vec
[i
].clear();
}
return 0;
}
