题意：
就是给你一个树，然后你的大本营在1号点，每一秒你可以让一个军队移动一格，或者从大本营发出一个军队出发，问你最少多少时间可以把整个图占领完。只要军队走过的点就是被占领了。
思考：
首先对于占领每个点其实就是让叶子节点被占领了即可，这个很容易想到，然后就是怎么去贪心了，一个点想被占领要么直接从根节点派军队过来，要么从他的其中一个子树的最深点走过来。可以发现于一个点x，他有3个子树，每个子树的最大深度分别是a，b，c很明显的去贪心就是先走a，然后看看是否要回来，然后再走b，然后看看是否要回来，再走c。是否要回来的标准就是是否比直接从根节点过来更优。所以对于一个点有军队要么直接是dep[now]，要么就是从其中一个儿子转移过来后的花费。所以贪心去跑就行了。
害，当时写这题的时候，思维混乱了一点，处理每个点的最大深度的时候忘记和maxn[spot]取max了，只和dep[spot]取了个max，这个错误犯了好多次了，真傻逼草。反正以后能更新的都更新上。然后还有一点混乱的时候就是dfs里面对于dp[now]应该就是min(dep[now],ned)。我当时写的是dp[p]+1，因为dp的状态是到达这个点最小的花费是我自己定义的，没保证正确性。然后对于每次dfs(spot的时候)，可以送过去的最小值就是要么从前一个点回来pre要么就是当前的深度也就是min(pre+1,dep[now]+1)。但是当时我写的是dp[now]也就是把这个dp[now]当成无限用的了，这个做法不是dp，是贪心去做的，所以一个点的状态不能重复用的，害，我真傻逼。以后多多思考吧，相信自己的做法，多多思考，别慌就行。
代码：
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define PII pair<int,int >
#define pb push_back
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 5e6+10;
int T,n;
int dp[N];
int dep[N];
int maxn[N];
vector<int > e[N];
bool cmp(int a,int b)
{
return maxn[a]<maxn[b];
}
void get(int now,int p)
{
dep[now] = dep[p]+1;
maxn[now] = dep[now];
for(auto spot:e[now])
{
if(spot==p) continue;
get(spot,now);
maxn[now] = max(maxn[now],max(maxn[spot],dep[spot]));
}
}
void dfs(int now,int p,int ned)
{
dp[now] = min(dep[now],ned); //这里dp[now] = ned,因为我ned传过来就是最最优的，不用再取了，当然取了保险。
int sum = dp[now],pre = sum;
for(auto spot:e[now])
{
if(spot==p) continue;
int res = min(dep[now],pre);
dfs(spot,now,res+1);
pre = maxn[spot]-dep[now];
}
}
signed main()
{
IOS;
cin>>T;
for(int cs=1;cs<=T;cs++)
{
cin>>n;
for(int i=0;i<=n;i++)
{
dp[i] = maxn[i] = dep[i] = 0;
e[i].clear();
}
for(int i=2;i<=n;i++)
{
int x;
cin>>x;
e[x].pb(i);
}
dep[0] = -1;get(1,0);
for(int i=1;i<=n;i++)
{
sort(e[i].begin(),e[i].end(),cmp);
}
dfs(1,0,0);
int ans = 0;
for(int i=1;i<=n;i++)
{
if(e[i].size()==0)
ans += dp[i];
}
printf("Case #%lld: %lld\n",cs,ans);
}
return 0;
}
总结：
多多思考，别慌，稳住，有信心。
