#include <bits/stdc++.h>
using namespace std;
int n;
std::vector<int>child[100001];
void clearing(){
for(int i=0;i<100001;i++)child[i].clear();
n=1;
}
int tellhowmany(int current , int arr[] ){
int sum=0;
for(int i=0;i<child[current].size();i++){
int temp=tellhowmany(child[current][i] , arr );
sum+=temp;
}
arr[current]=sum+1;
return sum+1;
}
int main() {
int t;std::cin >> t;
while(t--){
clearing();
std::cin >> n;
for(int i=2;i<=n;i++){
int x;std::cin >> x;
child[x].push_back(i);
}
int arr[n+1]={0};
int x=tellhowmany(1,arr);
int current=1;int answer=0;
// for(int i=1;i<=n;i++){
// cout<<arr[i]<<" ";
// }cout<<"\n";
while(true){
answer+=arr[current];
// std::cout << "current : "<<current<<" "<<answer << std::endl;
if(child[current].size()==0){
break;
}
int max=0;int index=-1;
for(int i=0;i<child[current].size();i++){
int p=arr[child[current][i]];
if(max<p){
max=p;index=i;
}
}
current=child[current][index];
}
std::cout << answer << std::endl;
}
return 0;
}
PROBLEM : SUBMEXS Problem - CodeChef
MY ANSWER : CodeChef: Practical coding for everyone
PLZ HELP
after some time …
i got my mistake ,
the case where two subtrees are same there we have to see in both because answer can come wrong
11
1 1 2 2 3 3 4 5 6 6
the answer is 20 but giving 19
#include <bits/stdc++.h>
using namespace std;
long long int n;
std::vector<long long int>child[100001];
void clearing(){
for(long long int i=0;i<100001;i++)child[i].clear();
n=1;
}
long long int tellhowmany(int current , long long int arr[] ){
long long int sum=0;
for(long long int i=0;i<child[current].size();i++){
long long int temp=tellhowmany(child[current][i] , arr );
sum+=temp;
}
arr[current]=sum+1;
return sum+1;
}
long long int max(long long int j , long long int k){
return j>k?j:k;
}
long long int solve(long long int current,long long int arr[]){
long long int answer=0;
answer+=arr[current];
if(child[current].size()==0){
return answer;
}
long long int p=0;
for(long long int i=0;i<child[current].size();i++){
p=max(p,solve(child[current][i],arr));
}
answer+=p;
return answer;
}
int main() {
long long int t;std::cin >> t;
while(t--){
clearing();
std::cin >> n;
for(long long int i=2;i<=n;i++){
long long int x;std::cin >> x;
child[x].push_back(i);
}
long long int arr[n+1]={0};
long long int x=tellhowmany(1,arr);
long long int current=1 , answer=0;
// for(int i=1;i<=n;i++){
// cout<<arr[i]<<" ";
// }cout<<"\n";
// while(true){
// answer+=arr[current];
// // std::cout << "current : "<<current<<" "<<answer << std::endl;
// if(child[current].size()==0){
// break;
// }
// long long int max=0;long long int index=-1;
// for(int i=0;i<child[current].size();i++){
// long long int p=arr[child[current][i]];
// if(max<p){
// max=p;index=i;
// }
// }
// current=child[current][index];
// }
std::cout << solve(1,arr) << "\n";
}
return 0;
}
got it