题目链接
https://codeforces.com/gym/102769/problem/K
题意
给定一颗树，1号节点为根节点，1号节点上有无数个士兵，每次操作可以将一个士兵移动到相邻节点，为将所有点遍历一次的最小操作数是多少？
思路
一个士兵从一号节点出发必定走到某个叶子节点，因此我们可以枚举所有的叶子节点来计算答案， 每个叶子节点的贡献要么从另一个叶子节点派士兵过来或者一号节点派士兵过来，为了保证这样的合法性，我们用dfs序遍历来遍历每个叶子节点，dfs时应当先走(子树中离根节点距离最远的叶子节点最小）的子树。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 50;
vector<int> G[maxn];
int du[maxn];
ll sz_d[maxn];//子树中叶子节点离根节点最远的距离
ll d[maxn]; //到根节点距离
void dfs_d(int v, int fa){
sz_d[v] = d[v];
for(auto u : G[v]){
if(u != fa){
d[u] = d[v] + 1;
dfs_d(u, v);
sz_d[v] = max(sz_d[v], sz_d[u]);
}
}
}
bool cmp(const int &a, const int &b){
if(sz_d[a] < sz_d[b]) return a > b;//优先走小的
else return a < b;
}
vector<int> p;
void dfs_x(int v, int fa){//dfs序
p.push_back(v);
sort(G[v].begin(), G[v].end(), cmp);
for(auto u : G[v]){
if(u != fa){
dfs_x(u, v);
p.push_back(v);
}
}
}
void init(int n){
p.clear();
for(int i = 0;i <= n;i++){
G[i].clear();
du[i] = sz_d[i] = d[i] = 0;
}
}
int main()
{
std::ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
int t;
cin >> t;
int cas = 0;
while(t--){
int n;
cin >> n;
for(int i = 2;i <= n;i++){
int x;cin >> x;
G[i].push_back(x);du[i]++;
G[x].push_back(i);du[x]++;
}
dfs_d(1, 0);
dfs_x(1, 0);
ll cnt = 1;
ll ans = 0;
for(auto i : p){
if(du[i] == 1){
ans += min(cnt, d[i]);
cnt = 0;
}
cnt++;
}
init(n);
cout << "Case #" << ++cas << ": " << ans << "
";
}
return 0;
}