Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <random>
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- #define int ll
- typedef pair<int, int> pii;
- typedef pair<ll, ll> pll;
- typedef vector<int> vi;
- typedef vector< vi > vvi;
- typedef vector< vvi > vvvi;
- typedef vector<short> vs;
- typedef vector<vs> vvs;
- typedef vector<vvs> vvvs;
- typedef vector<ll> vl;
- typedef vector<vl> vvl;
- typedef vector<vvl> vvvl;
- typedef vector<ld> vld;
- typedef vector<vld> vvld;
- typedef vector<vvld> vvvld;
- typedef vector<string> vst;
- typedef vector<vst> vvst;
- typedef pair<ld, ld> pld;
- typedef complex<double> base;
- #define inmin(a, b) a = min(a, (b))
- #define inmax(a, b) a = max(a, (b))
- #define ALL(a) a.begin(),a.end()
- #define RALL(a) a.rbegin(),a.rend()
- #define sqr(x) ((x) * (x))
- #define fori(i, n) for(int i = 0; i < int(n); ++i)
- #define SZ(a) ((int)((a).size()))
- #define triple(T) tuple<T, T, T>
- #define quad(T) tuple<T, T, T, T>
- #define watch(x) cerr << (#x) << " = " << (x) << endl;
- #ifdef MAX_HOME
- #define cerr cout
- #else
- #define cerr if (false) cerr
- #endif
- const double PI = 2 * acos(0.0);
- #define rand shittttty_shit
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());
- const string DIGITS = "0123456789";
- const string ALPH = "abcdefghijklmnopqrstuvwxyz";
- template <class T0, class T1>
- inline ostream & operator << (ostream &out, pair<T0, T1> &a) {
- return out << "{" << a.first << ", " << a.second << "}";
- }
- template <class T0, class T1, class T2>
- inline ostream & operator << (ostream &out, tuple<T0, T1, T2> &a) {
- return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << "}";
- }
- template <class T0, class T1, class T2, class T3>
- inline ostream & operator << (ostream &out, tuple<T0, T1, T2, T3> &a) {
- return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ", " << get<3>(a) << "}";
- }
- template<class T>
- inline ostream & operator << (ostream &out, vector<T> &a) {
- out << "[";
- fori (i, a.size())
- out << a[i] << vector<string>{", ", "] "}[i + 1 == a.size()];
- return out;
- }
- void smain();
- signed main() {
- ios::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- #ifdef MAX_HOME
- freopen("input.txt", "r", stdin);
- clock_t start = clock();
- #endif
- cout << setprecision(12) << fixed;
- smain();
- #ifdef MAX_HOME
- cout << "\n\n\n\nTOTAL EXECUTION TIME: " << float( clock () - start ) / CLOCKS_PER_SEC << endl;
- #endif
- return 0;
- }
- const int N = 2e5 + 100;
- ll M[2];
- ll pwx[N][2];
- struct DoubleHash {
- ll a, b, cnt;
- };
- const DoubleHash operator + (const DoubleHash &f, const DoubleHash &s) {
- 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};
- }
- const bool operator < (const DoubleHash &f, const DoubleHash &s) {
- return f.a < s.a || (f.a == s.a && (f.b < s.b || (f.b == s.b && f.cnt < s.cnt)));
- }
- struct Tree {
- vector<DoubleHash> t;
- Tree(int n) {
- t.resize(n << 2);
- }
- void build(int v, int tl, int tr, vector<DoubleHash> &child) {
- if (tl == tr) {
- t[v] = child[tl];
- return;
- }
- int tm = tl + tr >> 1;
- build(v << 1, tl, tm, child);
- build(v << 1 | 1, tm + 1, tr, child);
- t[v] = t[v << 1] + t[v << 1 | 1];
- }
- void upd(int v, int tl, int tr, int pos, DoubleHash dh) {
- if (tl == tr) {
- t[v] = dh;
- return;
- }
- int tm = tl + tr >> 1;
- if (pos <= tm) upd(v << 1, tl, tm, pos, dh);
- else upd(v << 1 | 1, tm + 1, tr, pos, dh);
- t[v] = t[v << 1] + t[v << 1 | 1];
- }
- };
- set<DoubleHash> solve(vvi &_g, bool big, set<DoubleHash> prev) {
- int n = (int)_g.size() - 1;
- vvi g(n + 1);
- function<void(int, int)> hang;
- hang = [&] (int v, int par) -> void {
- for (int to : _g[v]) {
- if (to == par) continue;
- hang(to, v);
- g[v].push_back(to);
- }
- };
- vl cnt(n + 1, 0);
- vector<DoubleHash> hs(n + 1);
- function<void(int)> dfs;
- dfs = [&] (int v) -> void {
- for (int to : g[v]) dfs(to);
- cnt[v] = 1;
- vector<DoubleHash> child;
- for (int to : g[v]) {
- cnt[v] += cnt[to];
- child.push_back(hs[to]);
- }
- sort(ALL(child));
- hs[v] = {1, 1, 1};
- for (auto item : child) {
- hs[v] = hs[v] + item;
- }
- DoubleHash fin = {2, 2, 1};
- hs[v] = hs[v] + fin;
- };
- function<void(int, DoubleHash)> dfs2;
- vector<DoubleHash> res(n + 1);
- set<DoubleHash> ans;
- dfs2 = [&] (int v, DoubleHash hsup) -> void {
- if (big) {
- if (g[v].size() == 0) {
- if (prev.count(hsup)) {
- ans.insert({v, v, v});
- }
- }
- }
- ll cntup = n - cnt[v];
- vector<DoubleHash> child;
- child.push_back(hsup);
- for (int to : g[v]) {
- child.push_back(hs[to]);
- }
- sort(ALL(child));
- res[v] = {1, 1, 1};
- for (auto item : child) {
- res[v] = res[v] + item;
- }
- DoubleHash fin = {2, 2, 1};
- res[v] = res[v] + fin;
- if (!big) {
- ans.insert(res[v]);
- }
- Tree tree(child.size());
- int sz = child.size();
- tree.build(1, 0, sz - 1, child);
- for (int to : g[v]) {
- int ind = upper_bound(ALL(child), hs[to]) - child.begin();
- ind--;
- tree.upd(1, 0, sz - 1, ind, {0, 0, 0});
- DoubleHash lol = tree.t[1];
- DoubleHash st = {1, 1, 1};
- DoubleHash fin = {2, 2, 1};
- lol = st + lol + fin;
- dfs2(to, lol);
- tree.upd(1, 0, sz - 1, ind, hs[to]);
- }
- };
- hang(1, -1);
- dfs(1);
- dfs2(1, {0, 0, 0});
- if (big && g[1].size() == 1) {
- if (prev.count(hs[g[1][0]])) ans.insert({1, 1, 1});
- }
- return ans;
- }
- int geth(string s) {
- // int ret = 0;
- // int n = s.size();
- // for (int i = 0; i < n; ++i) {
- // ret = (ret * + (s[i] - '(' + 1)) % M;
- // }
- // return ret;
- }
- bool is_prime(ll x) {
- for (int i = 2; i * i <= x; ++i) if (x % i == 0) return false;
- return true;
- }
- void smain() {
- fori (z, 2) {
- M[z] = 1e9 + rng() % 10000000;
- ll x = 3 + rng() % 100;
- for (; !is_prime(M[z]); ++M[z]);
- for (; !is_prime(x); ++x);
- pwx[0][z] = 1;
- for (int i = 1; i < N; ++i) {
- pwx[i][z] = x * pwx[i - 1][z] % M[z];
- }
- }
- int n;
- cin >> n;
- vvi g1(n + 1);
- vvi g2(n + 2);
- fori (i, n - 1) {
- int u, v;
- cin >> u >> v;
- g1[u].push_back(v);
- g1[v].push_back(u);
- }
- fori (i, n) {
- int u, v;
- cin >> u >> v;
- g2[u].push_back(v);
- g2[v].push_back(u);
- }
- set<DoubleHash> dummy;
- set<DoubleHash> hashs = solve(g1, false, dummy);
- set<DoubleHash> ans = solve(g2, true, hashs);
- assert(!ans.empty());
- cout << (*ans.begin()).a;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement