fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. unordered_map<int, vector<int>> mp;
  5. vector<int> v, vis;
  6.  
  7. int dfs(int s)
  8. {
  9. 	if(vis[s]) return v[s];
  10. 	vis[s] = 1;
  11. 	int x = mp[s].size();
  12. 	for(auto k : mp[s])
  13. 	{
  14. 		x += dfs(k);
  15. 	}
  16. 	return v[s] = x;
  17. }
  18.  
  19. int main() {
  20. 	ios_base::sync_with_stdio(false);
  21. 	cin.tie(NULL);
  22. 	cout.tie(NULL);
  23. 	ll n, x;
  24. 	cin>> n;
  25.  
  26. 	for(int i=2; i<=n; i++)
  27. 	{
  28. 		cin>>x;
  29. 		mp[x].push_back(i);
  30. 	}
  31. 	v.assign(n+1, 0);
  32. 	vis.assign(n+1, 0);
  33. 	for(int i=1; i<=n; i++)
  34. 	{
  35. 		if(!vis[i])
  36. 		{
  37. 			dfs(i);
  38. 		}
  39. 	}
  40. 	for(int i=1; i<=n; i++)
  41. 	{
  42. 		cout<<v[i]<<" ";
  43. 	}
  44. 	return 0;
  45. }
Success #stdin #stdout 0.01s 5448KB
comments (?)
stdin
copy 
5
1 1 2 3
stdout
copy 
4 1 1 0 0
https://ideone.com/X7ZNdv
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!