Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <numeric>
- #include <cstring>
- #include <cassert>
- #include <bitset>
- #include <vector>
- typedef long long llong;
- const int MAXN = 500000 + 10;
- const int INF = 1e9;
- int n;
- struct Query
- {
- int idx;
- int to;
- char type;
- Query(){}
- Query(int _idx, int _to, char _type)
- {
- idx = _idx;
- to = _to;
- type = _type;
- }
- };
- std::vector <Query> queries[MAXN];
- std::vector <int> one[MAXN];
- std::vector <int> two[MAXN];
- std::vector <int> oneBegin[MAXN];
- std::vector <int> twoBegin[MAXN];
- std::vector <int> tourOne;
- std::vector <int> tourTwo;
- int newNum[MAXN];
- int inOne[MAXN];
- int inTwo[MAXN];
- int outOne[MAXN];
- int outTwo[MAXN];
- int tree[MAXN];
- int ans[MAXN];
- void buildTourOne(int node, int p)
- {
- // std::cout << "build tour one: " << node << '\n';
- tourOne.push_back(node);
- for (const int &i : oneBegin[node])
- {
- if (i == p) continue;
- buildTourOne(i, node);
- }
- }
- int timer = 1;
- void buildInOutTime(int node, int p)
- {
- inOne[node] = timer++;
- for (const int &i : one[node])
- {
- if (i == p) continue;
- buildInOutTime(i, node);
- }
- outOne[node] = timer - 1;
- }
- void buildTourTwo(int node, int p)
- {
- inTwo[node] = timer++;
- tourTwo.push_back(node);
- for (const int &i : two[node])
- {
- if (i == p) continue;
- buildTourTwo(i, node);
- }
- outTwo[node] = timer - 1;
- }
- int oneS[MAXN];
- int twoS[MAXN];
- void findOneS(int node, int p)
- {
- for (int &i : one[node])
- {
- if (i == p)
- {
- std::swap(i, one[node].back());
- one[node].pop_back();
- break;
- }
- }
- oneS[node] = 1;
- for (const int &i : one[node])
- {
- findOneS(i, node);
- oneS[node] += oneS[i];
- }
- }
- void findTwoS(int node, int p)
- {
- for (int &i : two[node])
- {
- if (i == p)
- {
- std::swap(i, two[node].back());
- two[node].pop_back();
- break;
- }
- }
- twoS[node] = 1;
- for (const int &i : two[node])
- {
- findTwoS(i, node);
- twoS[node] += twoS[i];
- }
- }
- void update(int idx, int value)
- {
- if (idx == 0) return;
- for (int pos = idx ; pos <= n ; pos += pos & (-pos))
- {
- tree[pos] += value;
- }
- }
- int query(int idx)
- {
- int res = 0;
- for (int pos = idx ; pos >= 1 ; pos -= pos & (-pos))
- {
- res += tree[pos];
- }
- return res;
- }
- int add[MAXN];
- void solve()
- {
- tourOne.push_back(0);
- tourTwo.push_back(0);
- buildTourOne(1, 0);
- for (int i = 1 ; i <= n ; ++i)
- {
- newNum[tourOne[i]] = i;
- }
- for (int i = 1 ; i <= n ; ++i)
- {
- for (const int &j : oneBegin[i])
- {
- // std::cout << "edge: " << i << ' ' << j << ' ' << newNum[i] << ' ' << newNum[j] << '\n';
- one[newNum[i]].push_back(newNum[j]);
- }
- for (const int &j : twoBegin[i])
- {
- two[newNum[i]].push_back(newNum[j]);
- }
- }
- buildInOutTime(1, 0);
- findOneS(1, 0);
- findTwoS(1, 0);
- for (int i = 1 ; i <= n ; ++i)
- {
- std::sort(two[i].begin(), two[i].end(), [&](int x, int y)
- {
- return twoS[x] < twoS[y];
- });
- }
- timer = 1;
- buildTourTwo(1, 0);
- for (int i = 1 ; i <= n ; ++i)
- {
- for (const int &j : one[i])
- {
- int size = n - oneS[j];
- int l = -1, r = two[i].size(), mid;
- while (l < r - 1)
- {
- mid = (l + r) / 2;
- if (n - twoS[two[i][mid]] >= size) l = mid;
- else r = mid;
- }
- if (r < two[i].size())
- {
- int rr = outOne[j];
- int ll = inOne[j];
- queries[outTwo[i]].push_back({rr, j, '+'});
- queries[inTwo[two[i][r]] - 1].push_back({rr, j, '-'});
- queries[outTwo[i]].push_back({ll - 1, j, '-'});
- queries[inTwo[two[i][r]] - 1].push_back({ll - 1, j, '+'});
- }
- if (twoS[i] < size)
- {
- queries[n].push_back({outOne[j], j, '+'});
- queries[n].push_back({inOne[j] - 1, j, '-'});
- queries[outTwo[i]].push_back({outOne[j], j, '-'});
- queries[inTwo[i] - 1].push_back({outOne[j], j, '+'});
- queries[outTwo[i]].push_back({inOne[j] - 1, j, '+'});
- queries[inTwo[i] - 1].push_back({inOne[j] - 1, j, '-'});
- }
- }
- if (i == 1) continue;
- int size = oneS[i];
- int l = -1, r = two[i].size(), mid;
- while (l < r - 1)
- {
- mid = (l + r) / 2;
- if (n - twoS[two[i][mid]] >= size) l = mid;
- else r = mid;
- }
- if (r < two[i].size())
- {
- queries[outTwo[i]].push_back({n, 1, '+'});
- queries[outTwo[i]].push_back({outOne[i], 1, '-'});
- queries[outTwo[i]].push_back({inOne[i] - 1, 1, '+'});
- queries[inTwo[two[i][r]] - 1].push_back({n, 1, '-'});
- queries[inTwo[two[i][r]] - 1].push_back({outOne[i], 1, '+'});
- queries[inTwo[two[i][r]] - 1].push_back({inOne[i] - 1, 1, '-'});
- }
- if (twoS[i] < size)
- {
- queries[n].push_back({n, 1, '+'});
- queries[n].push_back({outOne[i], 1, '-'});
- queries[n].push_back({inOne[i] - 1, 1, '+'});
- queries[outTwo[i]].push_back({n, 1, '-'});
- queries[inTwo[i] - 1].push_back({n, 1, '+'});
- queries[outTwo[i]].push_back({outOne[i], 1, '+'});
- queries[outTwo[i]].push_back({inOne[i] - 1, 1, '-'});
- queries[inTwo[i] - 1].push_back({outOne[i], 1, '-'});
- queries[inTwo[i] - 1].push_back({inOne[i] - 1, 1, '+'});
- }
- }
- for (int i = n ; i >= 1 ; --i)
- {
- for (const Query &curr : queries[i])
- {
- if (curr.type == '+') update(curr.idx, 1);
- else update(curr.idx, -1);
- }
- add[tourTwo[i]] = query(n) - query(tourTwo[i] - 1);
- }
- for (int i = 1 ; i <= n ; ++i)
- {
- ans[tourOne[i]] = add[i];
- }
- }
- void output()
- {
- for (int i = 1 ; i <= n ; ++i)
- {
- std::cout << ans[i] << ' ';
- }
- std::cout << '\n';
- }
- void input()
- {
- int x, y;
- std::cin >> n;
- for (int i = 2 ; i <= n ; ++i)
- {
- std::cin >> x >> y;
- oneBegin[x].push_back(y);
- oneBegin[y].push_back(x);
- }
- for (int i = 2 ; i <= n ; ++i)
- {
- std::cin >> x >> y;
- twoBegin[x].push_back(y);
- twoBegin[y].push_back(x);
- }
- }
- void fastIO()
- {
- std::ios_base :: sync_with_stdio(0);
- std::cout.tie(nullptr);
- std::cin.tie(nullptr);
- }
- int main()
- {
- fastIO();
- input();
- solve();
- output();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement