Advertisement
mickypinata

SPOJ: Tree Isomorphism

Dec 7th, 2021
425
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define f first
  5. #define s second
  6. typedef long long lli;
  7. typedef pair<int, int> pii;
  8. typedef pair<lli, lli> pll;
  9.  
  10. const int N = 1e5 + 5;
  11. const int P0 = 1e4 + 7;
  12. const int P2 = 1e9 + 7;
  13. const int P1 = 98765431;
  14.  
  15. vector<int> adj[N];
  16. int nVertex, rnk[N];
  17.  
  18. void DFS(int u, int p, int depth){
  19.     rnk[u] = depth;
  20.     for(int v : adj[u]){
  21.         if(v == p){
  22.             continue;
  23.         }
  24.         DFS(v, u, depth + 1);
  25.     }
  26. }
  27.  
  28. int findFarthest(int r){
  29.     DFS(r, 0, 1);
  30.     int mx = 0;
  31.     int rt = 0;
  32.     for(int u = 1; u <= nVertex; ++u){
  33.         if(rnk[u] > mx){
  34.             mx = rnk[u];
  35.             rt = u;
  36.         }
  37.     }
  38.     return rt;
  39. }
  40.  
  41. vector<int> sq;
  42. pii DFSCenter(int u, int p, int ed){
  43.     sq.push_back(u);
  44.     if(u == ed){
  45.         int m = ((int)sq.size() - 1) / 2;
  46.         if(sq.size() % 2 == 0){
  47.             return pii(sq[m], sq[m + 1]);
  48.         }
  49.         return pii(sq[m], 0);
  50.     }
  51.     for(int v : adj[u]){
  52.         if(v == p){
  53.             continue;
  54.         }
  55.         pii nxt = DFSCenter(v, u, ed);
  56.         if(nxt.f != 0){
  57.             return nxt;
  58.         }
  59.     }
  60.     sq.pop_back();
  61.     return pii(0, 0);
  62. }
  63.  
  64. lli treeIso(int u, int p){
  65.     vector<lli> chd;
  66.     for(int v : adj[u]){
  67.         if(v == p){
  68.             continue;
  69.         }
  70.         chd.push_back(treeIso(v, u));
  71.     }
  72.     sort(chd.begin(), chd.end());
  73.     lli rt = P0;
  74.     for(lli x : chd){
  75.         rt = ((rt * P1) ^ x) % P2;
  76.     }
  77.     return rt;
  78. }
  79.  
  80. pll hshTree(){
  81.     for(int i = 1; i <= nVertex; ++i){
  82.         adj[i].clear();
  83.     }
  84.     for(int i = 1; i < nVertex; ++i){
  85.         int u, v;
  86.         scanf("%d%d", &u, &v);
  87.         adj[u].push_back(v);
  88.         adj[v].push_back(u);
  89.     }
  90.     int u = findFarthest(1);
  91.     int v = findFarthest(u);
  92.     sq.clear();
  93.     pii ct = DFSCenter(u, 0, v);
  94.     if(ct.s == 0){
  95.         return pll(treeIso(ct.f, 0), 0);
  96.     } else {
  97.         return pll(treeIso(ct.f, 0), treeIso(ct.s, 0));
  98.     }
  99. }
  100.  
  101. int main(){
  102.  
  103.     int Q;
  104.     scanf("%d", &Q);
  105.     while(Q--){
  106.         scanf("%d", &nVertex);
  107.         pll a = hshTree();
  108.         pll b = hshTree();
  109.         bool isSame = false;
  110.         if(a.s == 0 && b.s == 0){
  111.             isSame = (a.f == b.f);
  112.         } else if(a.s != 0 && b.s != 0){
  113.             isSame = (a.f == b.f) || (a.s == b.f);
  114.         }
  115.         if(isSame){
  116.             cout << "YES\n";
  117.         } else {
  118.             cout << "NO\n";
  119.         }
  120.     }
  121.  
  122.     return 0;
  123. }
  124.  
Advertisement
RAW Paste Data Copied
Advertisement