fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. vector<ll> dp;
  5. ll id;
  6. map<vector<ll>,ll> mp;
  7. void dfs(ll node,vector<ll>& vis,vector<vector<ll>>& adj,vector<ll>& parent){
  8.    vis[node]=1;
  9.         for (auto u :adj[node]) {
  10.         if (vis[u]==0) {
  11.             parent[u]=node;
  12.             dfs(u,vis,adj,parent);
  13.         } 
  14.     }
  15.     vector<ll> a; 
  16.     for (auto u :adj[node]) {
  17.         if (u != parent[node]) {
  18.             a.push_back(dp[u]);
  19.         }
  20.     }
  21.     if (!a.empty()) {
  22.         sort(a.begin(), a.end()); 
  23.     }
  24.     if (mp.find(a)==mp.end()) {
  25.         mp[a]=id;
  26.         dp[node]=id; 
  27.         id++; 
  28.     } else {
  29.         dp[node]=mp[a];
  30.     }
  31. }
  32.  
  33.  
  34. int main() {
  35. 	// your code goes here
  36. 	id=1;
  37.     ll n;
  38.     cin>>n;
  39.     dp.assign(n+1,0); 
  40.     vector<vector<ll>> adj(n+1); 
  41.     for (ll i=1;i<=n-1;i++) {
  42.         ll u,v;
  43.         cin>>u>>v; 
  44.         adj[u].push_back(v); 
  45.         adj[v].push_back(u); 
  46.     }
  47.     vector<ll> vis(n+1,0); 
  48.     vector<ll> parent(n+1,0); 
  49.     parent[1]=-1; 
  50.  
  51.     dfs(1,vis,adj,parent);
  52.     cout<<mp.size();
  53. 	return 0;
  54. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
13
1 2
1 3
1 10
1 11
2 4
2 5
3 6
3 7
6 8
7 9
11 12
11 13
stdout
copy 
5
https://ideone.com/wmWGi9
-> Given a general tree of “N” nodes(rooted at node 1) - find the count of distinct subtrees in it.

-> Two subtrees are distinct if they are structurally(isomorphically) different.
language:
C++ (gcc 8.3)
created:
8 days 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!