分析：
设dp[u]表示从征服u结点开始，到征服完整个子树需要的最少时间，先上个图。 贪心的策略是：先访问深度较小的u的子树vi，然后考虑次浅的子树vj的时候，兵来源有两个，一个是root，一个是vi最深的孩子，两者取较小的即可。 这里先抛一个结论：对于当前根节点u，设其儿子v1， v2。转移只可能由v1最深的儿子或者root，转移到v2最深的儿子。
代码：
#include <bits/stdc++.h>
using namespace std
;
typedef long long ll
;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define x first
#define y second
typedef pair
<int, int> par
;
const ll mod
= 1e9 + 7;
const int maxn
= 1e6 + 10;
const int inf
= 0x3f3f3f3f;
int n
;
vector
<int> g
[maxn
];
ll dp
[maxn
];
int dfs(int u
, int dep
)
{
if(g
[u
].size() == 0) return dep
;
vector
<int> len
;
for(int v
: g
[u
])
{
len
.pb(dfs(v
, dep
+ 1) - dep
);
dp
[u
] += dp
[v
] + 1;
}
sort(len
.begin(), len
.end());
for(int i
= 0; i
< len
.size() - 1; i
++)
dp
[u
] += min(dep
, len
[i
]);
return len
[len
.size() - 1] + dep
;
}
int main()
{
int t
; cin
>> t
;
int cases
= 0;
while(t
--)
{
int n
; cin
>> n
;
for(int i
= 1; i
<= n
; i
++) g
[i
].clear(), dp
[i
] = 0;
for(int i
= 2; i
<= n
; i
++)
{
int x
; scanf("%d", &x
);
g
[x
].pb(i
);
}
dfs(1, 0);
printf("Case #%d: %lld\n", ++cases
, dp
[1]);
}
}
