题意： 一棵树，每次可以花费1时间从根节点派出一个士兵前往相邻的节点，或者指挥其他节点上的士兵往相邻节点移动，求士兵遍历完整棵树的最小花费，1是根节点，一开始只有根节点有士兵 题解： 可以将问题转化为，走完所有的叶子节点所需要的时间。 我们需要做的就是维护根节点到叶子节点的距离和相邻叶子节点到叶子节点的距离的最小值，我们先算出以i节点为根节点的子树中的叶子节点到i的最远距离，然后对最远距离进行排序，再对树进行一次遍历，算出根节点到i节点的距离和i节点到子树中叶子节点的最小距离，两者取最小值，就是到达i的最小值。 代码：
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #include<map> #include<stack> #include<set> #define iss ios::sync_with_stdio(false) using namespace std; typedef unsigned long long ull; typedef long long ll; typedef pair<int ,int > pii; const ll mod=998244353; const ll INF=0x3f3f3f3f; const int MAXN=1e6+5; int deep[MAXN]; int ans[MAXN]; std::vector<pii> v1[MAXN]; int dfs(int u,int f,int d) { deep[u]=d; if(v1[u].size()==0) return 1; for(int i=0;i<v1[u].size();i++) { int v=v1[u][i].second; if(v==f) continue; int maxx=dfs(v,u,d+1); //cout<<v<<" "<<maxx<<endl; v1[u][i].first=maxx; } sort(v1[u].begin(),v1[u].end()); return v1[u].back().first+1; } int solve(int u,int f,int d) { ans[u]=d; if(v1[u].size()==0) { cout<<u<<" "<<d<<endl; } int minn=d; for(int i=0;i<v1[u].size();i++) { int v=v1[u][i].second; if(v==f) continue; minn=min(deep[u],solve(v,u,minn+1)); } return minn+1; } int main() { int t; int kase=1; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { v1[i].clear(); } int fa; for(int i=2;i<=n;i++) { scanf("%d",&fa); v1[fa].push_back(make_pair(0,i)); } dfs(1,-1,0); solve(1,-1,0); ll sum=0; for(int i=1;i<=n;i++) { if(v1[i].size()==0) { sum+=ans[i]; } } printf("Case #%d: %lld\n",kase++,sum); } }