K - Kingdom’s Power
比赛的时候思路出了 但不会证。
赛后敲了就过了。
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
#define ll long long
int n;
vector <pair<int, int>> tr[N];
int depth[N];
int val[N];
int dfs1(int u, int dep) {
if(tr[u].empty()) return 1;
depth[u] = dep;
for(auto &x : tr[u])
x.first = dfs1(x.second, dep+1);
sort(tr[u].begin(), tr[u].end());
return tr[u].back().first + 1;
}
int dfs2(int u, int Val) {
val[u] = Val;
if(tr[u].empty()) return 1;
int minl = Val;
for(auto &x : tr[u]) {
minl = min(depth[u], dfs2(x.second, minl+1));
}
return minl + 1;
}
int main() {
int t;
int fa;
scanf("%d", &t);
for(int Case = 1;Case <= t;Case ++) {
scanf("%d", &n);
for(int i = 1;i <= n;i ++) tr[i].clear();
for(int i = 2;i <= n;i ++) {
scanf("%d", &fa);
tr[fa].push_back(make_pair(0, i));
}
dfs1(1, 0);
dfs2(1, 0);
ll ans=0;
for(int i=1;i<=n;i++)
if(tr[i].empty())
ans+=val[i];
printf("Case #%d: %d\n", Case, ans);
}
}