CSES Tree Algorithms : 1. Subordinates

CSES Tree Algorithms

1. Subordinates

link

	#include<bits/stdc++.h>
	using namespace std;
	int help(vector<vector<int>>&tr,int u,vector<int>&dp){
	if(dp[u]!=-1)return dp[u];
	int c=0;
	for(auto v:tr[u]){
	c+= (1+help(tr,v,dp));
	}
	return dp[u]=c;
	}
	int main(){
	system("CLS");
	int n;cin>>n;
	vector<int>v(n-1);
	for(auto &it:v)cin>>it;
	vector<vector<int>>tr(n+1);
	for(int i=0;i<n-1;++i){
	tr[v[i]].push_back(i+2);
	}
	vector<int>ans;
	vector<int>dp(n+1,-1);
	for(int i=1;i<=n;++i){
	int k=help(tr,i,dp);
	ans.push_back(k);
	}
	for(auto it:ans)
	cout<<it<<" ";
	return 0;
	};

view raw subordinates hosted with ❤ by GitHub