fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef long long int ll;
  7.  
  8. ll id=1;
  9.  
  10. void dfs(ll node , vector<ll> g[] , vector<ll> &dp , vector<ll> &visited , map<vector<ll>,ll> &mpp
  11. , vector<ll> &parent){
  12.  
  13. 	visited[node]=1;
  14.  
  15.     for(auto it : g[node]){
  16.  
  17. 	if(!visited[it]){
  18. 		parent[it] = node;
  19. 		dfs(it , g , dp , visited,mpp,parent);
  20. 	}
  21. }
  22.  
  23. 	vector<ll> a;
  24.  
  25. 	for(auto it : g[node]){
  26. 	if(it!=parent[node]){
  27. 		a.push_back(dp[it]);
  28. 	}
  29. 	}
  30.  
  31. 	sort(a.begin(),a.end());
  32.  
  33. 	if(mpp.find(a)==mpp.end()){
  34. 		mpp[a]=id;
  35. 		id++;
  36. 	}
  37. 	dp[node] = mpp[a];
  38.  
  39. 	cout<<node<<" "<<dp[node]<<endl;
  40.  
  41.  
  42. }
  43.  
  44. int main() {
  45.  
  46. 	ll n;
  47. 	cin>>n;
  48.  
  49. 	vector<ll> g[n+1];
  50.  
  51. 	for(ll i=1;i<n;i++){
  52. 		ll u;
  53. 		ll v;
  54. 		cin>>u>>v;
  55. 		g[u].push_back(v);
  56. 		g[v].push_back(u);
  57. 	}
  58.  
  59. 	vector<ll> dp(n+1,0);
  60. 	vector<ll> visited(n+1,0);
  61. 	vector<ll> parent(n+1,-1);
  62.  
  63. 	map<vector<ll>,ll> mpp;
  64.  
  65. 	ll node = 1;
  66.  
  67. 	dfs(node, g , dp , visited , mpp ,parent);
  68.  
  69. 	cout<<"total number of different subtrees "<<dp[node]<<endl;
  70.  
  71.  
  72. 	return 0;
  73. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
7
1 2
1 3
3 6
3 7
2 4
2 5
stdout
copy 
4 1
5 1
2 2
6 1
7 1
3 2
1 3
total number of different subtrees 3
https://ideone.com/5RRRa6
language:
C++14 (gcc 8.3)
created:
1 day 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!