SHARE
TWEET

Untitled

a guest Jul 23rd, 2019 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <random>
  3.  
  4. using namespace std;
  5.  
  6. typedef unsigned long long ull;
  7. typedef long long ll;
  8. typedef long double ld;
  9. #define int ll
  10. typedef pair<int, int> pii;
  11. typedef pair<ll, ll> pll;
  12. typedef vector<int> vi;
  13. typedef vector< vi > vvi;
  14. typedef vector< vvi > vvvi;
  15. typedef vector<short> vs;
  16. typedef vector<vs> vvs;
  17. typedef vector<vvs> vvvs;
  18. typedef vector<ll> vl;
  19. typedef vector<vl> vvl;
  20. typedef vector<vvl> vvvl;
  21. typedef vector<ld> vld;
  22. typedef vector<vld> vvld;
  23. typedef vector<vvld> vvvld;
  24. typedef vector<string> vst;
  25. typedef vector<vst> vvst;
  26. typedef pair<ld, ld> pld;
  27. typedef complex<double> base;
  28.  
  29. #define inmin(a, b) a = min(a, (b))
  30. #define inmax(a, b) a = max(a, (b))
  31. #define ALL(a) a.begin(),a.end()
  32. #define RALL(a) a.rbegin(),a.rend()
  33. #define sqr(x) ((x) * (x))
  34. #define fori(i, n) for(int i = 0; i < int(n); ++i)
  35. #define SZ(a) ((int)((a).size()))
  36. #define triple(T) tuple<T, T, T>
  37. #define quad(T) tuple<T, T, T, T>
  38. #define watch(x) cerr << (#x) << " = " << (x) << endl;
  39.  
  40. #ifdef MAX_HOME
  41. #define cerr cout
  42. #else
  43. #define cerr if (false) cerr
  44. #endif
  45.  
  46. const double PI = 2 * acos(0.0);
  47. #define rand shittttty_shit
  48. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  49. mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());
  50.  
  51. const string DIGITS = "0123456789";
  52. const string ALPH = "abcdefghijklmnopqrstuvwxyz";
  53.  
  54. template <class T0, class T1>
  55. inline ostream & operator << (ostream &out, pair<T0, T1> &a) {
  56.     return out << "{" << a.first << ", " << a.second << "}";
  57. }
  58.  
  59. template <class T0, class T1, class T2>
  60. inline ostream & operator << (ostream &out, tuple<T0, T1, T2> &a) {
  61.     return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << "}";
  62. }
  63.  
  64. template <class T0, class T1, class T2, class T3>
  65. inline ostream & operator << (ostream &out, tuple<T0, T1, T2, T3> &a) {
  66.     return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ", " <<  get<3>(a) << "}";
  67. }
  68.  
  69. template<class T>
  70. inline ostream & operator << (ostream &out, vector<T> &a) {
  71.     out << "[";
  72.     fori (i, a.size())
  73.         out << a[i] << vector<string>{", ", "]  "}[i + 1 == a.size()];
  74.     return out;
  75. }
  76.  
  77.  
  78.  
  79. void smain();
  80.  
  81. signed main() {
  82.     ios::sync_with_stdio(0);
  83.     cin.tie(0); cout.tie(0);
  84.  
  85. #ifdef MAX_HOME
  86.     freopen("input.txt", "r", stdin);
  87.     clock_t start = clock();
  88. #endif
  89.     cout << setprecision(12) << fixed;
  90.     smain();
  91. #ifdef MAX_HOME
  92.     cout << "\n\n\n\nTOTAL EXECUTION TIME: " << float( clock () - start ) /  CLOCKS_PER_SEC << endl;
  93. #endif
  94.     return 0;
  95. }
  96.  
  97.  
  98. const int N = 2e5 + 100;
  99. ll M[2];
  100. ll pwx[N][2];
  101.  
  102. struct DoubleHash {
  103.     ll a, b, cnt;
  104. };
  105.  
  106. const DoubleHash operator + (const DoubleHash &f, const DoubleHash &s) {
  107.     return {(f.a * pwx[s.cnt][0] + s.a) % M[0], (f.b * pwx[s.cnt][1] + s.b) % M[1], f.cnt + s.cnt};
  108. }
  109.  
  110. const bool operator < (const DoubleHash &f, const DoubleHash &s) {
  111.     return f.a < s.a || (f.a == s.a && (f.b < s.b || (f.b == s.b && f.cnt < s.cnt)));
  112. }
  113.  
  114. struct Tree {
  115.     vector<DoubleHash> t;
  116.     Tree(int n) {
  117.         t.resize(n << 2);
  118.     }
  119.  
  120.  
  121.     void build(int v, int tl, int tr, vector<DoubleHash> &child) {
  122.         if (tl == tr) {
  123.             t[v] = child[tl];
  124.             return;
  125.         }
  126.         int tm = tl + tr >> 1;
  127.         build(v << 1, tl, tm, child);
  128.         build(v << 1 | 1, tm + 1, tr, child);
  129.         t[v] = t[v << 1] + t[v << 1 | 1];
  130.     }
  131.  
  132.     void upd(int v, int tl, int tr, int pos, DoubleHash dh) {
  133.         if (tl == tr) {
  134.             t[v] = dh;
  135.             return;
  136.         }
  137.         int tm = tl + tr >> 1;
  138.         if (pos <= tm) upd(v << 1, tl, tm, pos, dh);
  139.         else upd(v << 1 | 1, tm + 1, tr, pos, dh);
  140.         t[v] = t[v << 1] + t[v << 1 | 1];
  141.     }
  142. };
  143.  
  144. set<DoubleHash> solve(vvi &_g, bool big, set<DoubleHash> prev) {
  145.  
  146.     int n = (int)_g.size() - 1;
  147.     vvi g(n + 1);
  148.     function<void(int, int)> hang;
  149.  
  150.     hang = [&] (int v, int par) -> void {
  151.         for (int to : _g[v]) {
  152.             if (to == par) continue;
  153.             hang(to, v);
  154.             g[v].push_back(to);
  155.         }
  156.     };
  157.  
  158.     vl cnt(n + 1, 0);
  159.     vector<DoubleHash> hs(n + 1);
  160.  
  161.     function<void(int)> dfs;
  162.  
  163.     dfs = [&] (int v) -> void {
  164.         for (int to : g[v]) dfs(to);
  165.         cnt[v] = 1;
  166.         vector<DoubleHash> child;
  167.         for (int to : g[v]) {
  168.             cnt[v] += cnt[to];
  169.             child.push_back(hs[to]);
  170.         }
  171.         sort(ALL(child));
  172.         hs[v] = {1, 1, 1};
  173.         for (auto item : child) {
  174.             hs[v] = hs[v] + item;
  175.         }
  176.         DoubleHash fin = {2, 2, 1};
  177.         hs[v] = hs[v] + fin;
  178.     };
  179.  
  180.     function<void(int, DoubleHash)> dfs2;
  181.     vector<DoubleHash> res(n + 1);
  182.     set<DoubleHash> ans;
  183.     dfs2 = [&] (int v, DoubleHash hsup) -> void {
  184.         if (big) {
  185.             if (g[v].size() == 0) {
  186.                 if (prev.count(hsup)) {
  187.                     ans.insert({v, v, v});
  188.                 }
  189.             }
  190.         }
  191.         ll cntup = n - cnt[v];
  192.         vector<DoubleHash> child;
  193.         child.push_back(hsup);
  194.         for (int to : g[v]) {
  195.             child.push_back(hs[to]);
  196.         }
  197.         sort(ALL(child));
  198.         res[v] = {1, 1, 1};
  199.         for (auto item : child) {
  200.             res[v] = res[v] + item;
  201.         }
  202.         DoubleHash fin = {2, 2, 1};
  203.         res[v] = res[v] + fin;
  204.         if (!big) {
  205.             ans.insert(res[v]);
  206.         }
  207.         Tree tree(child.size());
  208.         int sz = child.size();
  209.         tree.build(1, 0, sz - 1, child);
  210.  
  211.         for (int to : g[v]) {
  212.             int ind = upper_bound(ALL(child), hs[to]) - child.begin();
  213.             ind--;
  214.  
  215.             tree.upd(1, 0, sz - 1, ind, {0, 0, 0});
  216.             DoubleHash lol = tree.t[1];
  217.             DoubleHash st = {1, 1, 1};
  218.             DoubleHash fin = {2, 2, 1};
  219.             lol = st + lol + fin;
  220.  
  221.             dfs2(to, lol);
  222.             tree.upd(1, 0, sz - 1, ind, hs[to]);
  223.         }
  224.     };
  225.  
  226.  
  227.     hang(1, -1);
  228.     dfs(1);
  229.     dfs2(1, {0, 0, 0});
  230.  
  231.     if (big && g[1].size() == 1) {
  232.         if (prev.count(hs[g[1][0]])) ans.insert({1, 1, 1});
  233.     }
  234.     return ans;
  235. }
  236.  
  237. int geth(string s) {
  238. //    int ret = 0;
  239. //    int n = s.size();
  240. //    for (int i = 0; i < n; ++i) {
  241. //        ret = (ret *  + (s[i] - '(' + 1)) % M;
  242. //    }
  243. //    return ret;
  244. }
  245.  
  246. bool is_prime(ll x) {
  247.     for (int i = 2; i * i <= x; ++i) if (x % i == 0) return false;
  248.     return true;
  249. }
  250.  
  251. void smain() {
  252.  
  253.     fori (z, 2) {
  254.         M[z] = 1e9 + rng() % 10000000;
  255.         ll x = 3 + rng() % 100;
  256.         for (; !is_prime(M[z]); ++M[z]);
  257.         for (; !is_prime(x); ++x);
  258.         pwx[0][z] = 1;
  259.         for (int i = 1; i < N; ++i) {
  260.             pwx[i][z] = x * pwx[i - 1][z] % M[z];
  261.         }
  262.     }
  263.  
  264.  
  265.  
  266.     int n;
  267.     cin >> n;
  268.     vvi g1(n + 1);
  269.     vvi g2(n + 2);
  270.  
  271.     fori (i, n - 1) {
  272.         int u, v;
  273.         cin >> u >> v;
  274.         g1[u].push_back(v);
  275.         g1[v].push_back(u);
  276.     }
  277.     fori (i, n) {
  278.         int u, v;
  279.         cin >> u >> v;
  280.         g2[u].push_back(v);
  281.         g2[v].push_back(u);
  282.     }
  283.  
  284.     set<DoubleHash> dummy;
  285.     set<DoubleHash> hashs = solve(g1, false, dummy);
  286.     set<DoubleHash> ans = solve(g2, true, hashs);
  287.     assert(!ans.empty());
  288.     cout << (*ans.begin()).a;
  289. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top