https://vjudge.net/contest/402960#problem/J
Alex is a professional computer game player.
These days, Alex is playing a war strategy game. The kingdoms in the world form a rooted tree. Alex's kingdom 11 is the root of the tree. With his great diplomacy and leadership, his kingdom becomes the greatest empire in the world. Now, it's time to conquer the world!
Alex has almost infinite armies, and all of them are located at 11 initially. Every week, he can command one of his armies to move one step to an adjacent kingdom. If an army reaches a kingdom, that kingdom will be captured by Alex instantly.
Alex would like to capture all the kingdoms as soon as possible. Can you help him?
Input
The first line of the input gives the number of test cases, T (1≤T≤105)T (1≤T≤105). TT test cases follow.
For each test case, the first line contains an integer n (1≤n≤106)n (1≤n≤106), where nn is the number of kingdoms in the world.
The next line contains (n−1)(n−1) integers f2,f3,⋯,fn (1≤fi<i)f2,f3,⋯,fn (1≤fi<i), representing there is a road between fifi and ii.
The sum of nn in all test cases doesn't exceed 5×1065×106.
Output
For each test case, output one line containing "Case #x: y", where xx is the test case number (starting from 11), and yy is the minimum time to conquer the world.
Example
Input
2 3 1 1 6 1 2 3 4 4Output
Case #1: 2 Case #2: 6Sponsor
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include<unordered_map> using namespace std; typedef long long ll; const ll maxn=1e6+10,inf=1<<29; ll mod=1e9+7; ll t,n,m,ans,s; ll vis[maxn],dis[maxn]; ll f[maxn]; ll dp[maxn]; int main() { cin>>t; for(int o=1;o<=t;o++) { scanf("%lld",&n); for(int i=2;i<=n;i++) { scanf("%lld",&f[i]); dp[i]=0; dis[i]=0; } dp[1]=0; dis[1]=0; for(int i=2;i<=n;i++) { dis[i]=dis[f[i]]+1; } ans=0; for(int i=n;i>=2;i--) { if(dp[f[i]]<dp[i]+1) { ans+=dp[f[i]]+min(dp[f[i]],dis[f[i]]); dp[f[i]]=dp[i]+1; } else { if(dp[f[i]]==0) { dp[f[i]]=dp[i]+1; } else { ans+=dp[i]+1+min(dp[i]+1,dis[f[i]]); } } } ans+=dp[1]; printf("Case #%d: ",o); printf("%lld\n",ans); } return 0; }
