fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int const N=1e5+1,base=N+2,mod=1e9+7;
  4. bool odw[N];
  5. long long hsh1[N],hsh2[N],pot[N];
  6. vector<int>g1[N],g2[N],w[N];
  7.  
  8. void dfs1(int v){
  9.     odw[v]=1;
  10.     for(int i:g1[v]){
  11.         if(odw[i]==0){
  12.             dfs1(i);
  13.             w[v].push_back(hsh1[i]);
  14.         }
  15.     }
  16.     if(w[v].size()==0) hsh1[v]=base;
  17.     else{
  18.         sort(w[v].begin(),w[v].end());
  19.         for(int i=1;i<=w[v].size();i++) hsh1[v]=(hsh1[v]+w[v][i]*pot[i]%mod)%mod;
  20.     }
  21.     w[v].clear();
  22. }
  23.  
  24. void dfs2(int v){
  25.     odw[v]=1;
  26.     for(int i:g2[v]){
  27.         if(odw[i]==0){
  28.             dfs2(i);
  29.             w[v].push_back(hsh2[i]);
  30.         }
  31.     }
  32.     if(w[v].size()==0) hsh2[v]=base;
  33.     else{
  34.         sort(w[v].begin(),w[v].end());
  35.         for(int i=1;i<=w[v].size();i++) hsh2[v]=(hsh2[v]+w[v][i]*pot[i]%mod)%mod;
  36.     }
  37.     w[v].clear();
  38. }
  39.  
  40. int main(){
  41. 	ios_base::sync_with_stdio(0);
  42. 	cin.tie(0);
  43.     int n,a,b;
  44.     cin>>n; pot[0]=1;
  45.     for(int i=1;i<=n;i++) pot[i]=pot[i-1]*base%mod;
  46.     for(int i=1;i<n;i++){
  47.         cin>>a>>b;
  48.         g1[a].push_back(b);
  49.         g1[b].push_back(a);
  50.     }
  51.     for(int i=1;i<n;i++){
  52.         cin>>a>>b;
  53.         g2[a].push_back(b);
  54.         g2[b].push_back(a);
  55.     }
  56.     dfs1(1);
  57.     for(int i=0;i<=n;i++) odw[i]=0;
  58.     dfs2(1);
  59.     if(hsh1[1]==hsh2[1]) cout<<hsh1[1];
  60.     else cout<<"NIE";
  61. }
  62.  
Success #stdin #stdout 0.01s 12536KB
comments (?)
stdin
copy 
1
stdout
copy 
100003
https://ideone.com/3ukdZW
language:
C++ (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!