考场正解，可惜写挂了。
考虑模拟。
考虑如何最大化一个士兵的作用。
一个士兵首先肯定是一次性走到叶子是最优的，不然会有没有必要的重复路径。
先递归至叶子，然后回溯时将回溯到的节点设为\(lca\)。
然后处理\(lca\)的儿子。
非叶子节点会在向叶子走时就将其占领，所以答案在叶子结算。
接下来所说的节点只考虑叶子。
对于一个节点，有两种情况：
1、从根新派一个兵来这里。
2、让之前的士兵来这里。
1的花费是\(lca\)的深度+这个节点到\(lca\)的距离==这个节点的深度。
2的花费是上一个士兵现在的位置到\(lca\)的距离+这个节点到\(lca\)的距离。
只用比较前者就可以决定。
每次处理完一个叶子后将士兵的位置设为当前。
时间复杂度：\(\Theta\)(n)(一遍\(DFS\))。
Code
#include<bits/stdc++.h>
using namespace std;
namespace STD
{
#define rr register
typedef long long ll;
const int N=1e5+4;
int n,lca,now;
ll ans;
struct son
{
int id,h;
son(){}
son(int id_,int h_){id=id_,h=h_;}
bool operator<(const son b) const
{
return h<b.h;
}
};
vector<son> to[N];
int depth[N],fa[N];
int h[N];
bool leaf[N];
int read()
{
rr int x_read=0,y_read=1;
rr char c_read=getchar();
while(c_read<'0'||c_read>'9')
{
if(c_read=='-') y_read=-1;
c_read=getchar();
}
while(c_read<='9'&&c_read>='0')
{
x_read=(x_read<<3)+(x_read<<1)+(c_read^48);
c_read=getchar();
}
return x_read*y_read;
}
void dfs(int &x)
{
h[x]=1;
int temp=INT_MIN;
for(int i=0;i<to[x].size();i++)
{
if(to[x][i].id==fa[x]) continue;
fa[to[x][i].id]=x;
depth[to[x][i].id]=depth[x]+1;
dfs(to[x][i].id);
temp=max(temp,h[to[x][i].id]);
to[x][i].h=h[to[x][i].id];
}
if(temp!=INT_MIN)
h[x]+=temp;
else if(to[x].size()==1&&to[x][0].id==fa[x])
leaf[x]=1;
}
void deal(int &x)
{
if(leaf[x])
{
if(!now)
ans+=depth[x];
else
{
if(depth[now]-depth[lca]>depth[lca])
ans+=depth[x];
else
ans+=depth[now]-2*depth[lca]+depth[x];
}
now=x;
return;
}
sort(to[x].begin(),to[x].end());
for(int i=0;i<to[x].size();i++)
{
if(to[x][i].id==fa[x]) continue;
deal(to[x][i].id);
lca=x;
}
}
};
using namespace STD;
int main()
{
n=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
to[u].emplace_back(son(v,0));
to[v].emplace_back(son(u,0));
}
int root=1;
dfs(root);
deal(root);
cout<<ans;
}