题目链接: 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
];
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;
}
END
