题目链接: Kingdom’s Power
大致题意:
有一棵树，国王的国家在1号节点，他有无数只军队，每次可以使一支军队移动一步到相邻节点（不是所有出动的军队同时移动一步），军队到达的节点表示被国王征服，问最少移动几次军队可以征服所有节点
解题思路:
初始化f数组记录从根到每一个节点的距离（后面会用到）
假设，当前深度为10的结点A存在2条子链，左边的长度为3，右边的长度为5，那么最优的走法是从当前结点走向左边，再由左边的叶子走向右边的叶子
既然要求移动步数最少，所以我们要尽可能的利用叶子节点
这时我们思考，对于一个分支，我们选择从已经到叶子节点的军队移动到该分支的最深叶子节点，还是选择从根节点派一支新的军队移动到该分支的最深叶子节点，这时，我们需要判断两种选择哪种移动步数最少，这时候就会用到我们的f数组，判断叶子节点到该分支的步数和根节点到该分支的步数哪个更少（注意区分这里叶子节点是除了该分支最深叶子节点之外，其他的叶子节点）
其他细节看代码注释
空间复杂度O(N)
时间复杂度O(nlogn)
AC代码:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int f[N]; //叶子节点到每一个节点的距离
int a[N];
int n;
vector<int> e[N];
void dfs(int u) {
int dis = 0;for (auto v : e[u]) {
dfs(v);dis = max(dis, f[v]);}f[u] = dis + 1;
}
bool cmp(int a, int b) {
return f[a] < f[b];
}
ll dfs(int u, int fa, int depth) {
a[u] = a[fa] + 1;ll dis = a[u];for (int i = 0; i < e[u].size(); ++i) {
int j = e[u][i];//if (j == fa)continue; 单向边，不会遍历回到父节点dis = dfs(j, u, depth + 1);if (i != e[u].size() - 1) {
//子数最深的一个点，判断从叶子节点移动军队到该点更近，还是从根节点移动军队到该点更近a[u] = dis + min(f[j], depth);}}return dis;
}
int main() {
int t; cin >> t;for (int T = 1; T <= t; ++T) {
scanf("%d", &n);for (int i = 1; i <= n; ++i)e[i].clear();for (int v = 2; v <= n; ++v) {
int u; scanf("%d", &u);e[u].push_back(v);}dfs(1);for (int i = 1; i <= n; ++i) {
//目的是保留每个有分支的最深叶子节点if (e[i].size())sort(e[i].begin(), e[i].end(), cmp);}ll ans = 0;for (auto v : e[1]) {
ans += 1ll * dfs(v, 1, 1);//累加根节点每一个分支的最短距离}printf("Case #%d: %lld\n", T, ans);}return 0;
}