2020 CCPC 秦皇岛 K（贪心）

[题目链接](https://vjudge.net/problem/Gym-102769K) ------------ ------------ ```cpp #include <bits/stdc++.h> using namespace std; const int M=2e6+5; int n,ans,dep[M],head[M],nxt[M],ver[M],tot; priority_queue< pair<int,int> > pq[M]; void add(int x,int y) { nxt[++tot]=head[x]; head[x]=tot; ver[tot]=y; } int dfs1(int x,int fa) { dep[x]=dep[fa]+1; int res=0; for(int i=head[x];i;i=nxt[i]) { int y=ver[i]; if(y==fa)continue; int k=dfs1(y,x)+1; pq[x].push(make_pair(-k,y)); res=max(res,k); } return res; } int dfs2(int x,int cost) { if(pq[x].empty()) { ans+=min(dep[x],cost); return 0; } while(!pq[x].empty()) { int y=pq[x].top().second;pq[x].pop(); cost=dfs2(y,cost+1)+1; } return cost; } int main() { int T,cas=0;scanf("%d",&T); while(T--) { scanf("%d",&n); tot=0; for(int i=1;i<=n;i++)dep[i]=head[i]=0; for(int i=2;i<=n;i++) { int x;scanf("%d",&x); add(x,i);add(i,x); } ans=0; dep[0]=-1; dfs1(1,0); dfs2(1,0); printf("Case #%d: %d\n",++cas,ans); } return 0; } ```