fork(1) 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],poz[N];
  6. vector<int>g1[N],g2[N];
  7.  
  8. void dfs1(int v){
  9.     odw[v]=1;
  10.     for(int i:g1[v]){
  11.         if(odw[i]==0){
  12.         	poz[i]=poz[v]+1;
  13.             dfs1(i);
  14.             hsh1[v]=(hsh1[v]+hsh1[i])%mod;
  15.         }
  16.     }
  17.     hsh1[v]=hsh1[v]*poz[v]*base%mod;
  18. }
  19.  
  20. void dfs2(int v){
  21.     odw[v]=1;
  22.     for(int i:g2[v]){
  23.         if(odw[i]==0){
  24.         	poz[i]=poz[v]+1;
  25.             dfs2(i);
  26.             hsh2[v]=(hsh2[v]+hsh2[i])%mod;
  27.         }
  28.     }
  29.     hsh2[v]=hsh2[v]*poz[v]*base%mod;
  30. }
  31.  
  32. int main(){
  33. 	ios_base::sync_with_stdio(0);
  34. 	cin.tie(0);
  35.     int n,a,b;
  36.     cin>>n;
  37.     for(int i=1;i<n;i++){
  38.         cin>>a>>b;
  39.         g1[a].push_back(b);
  40.         g1[b].push_back(a);
  41.     }
  42.     for(int i=1;i<n;i++){
  43.         cin>>a>>b;
  44.         g2[a].push_back(b);
  45.         g2[b].push_back(a);
  46.     }
  47.     poz[1]=1;
  48.     dfs1(1);
  49.     for(int i=0;i<=n;i++) odw[i]=0, poz[i]=0;
  50.     poz[1]=1;
  51.     dfs2(1);
  52.     if(hsh1[1]==hsh2[1]) cout<<"TAK";
  53.     else cout<<"NIE";
  54. }
  55.  
Success #stdin #stdout 0.01s 10600KB
comments (?)
stdin
copy 
6
1 2
1 3
2 4
3 5
3 6
1 2
1 3
2 5
2 6
3 4
stdout
copy 
TAK
https://ideone.com/HeLlvd
language:
C++ (gcc 8.3)
created:
119 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!