Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- //#include <ext/pb_ds/assoc_container.hpp>
- #define pb push_back
- #define F first
- #define S second
- #define ll long long
- #define ull unsigned long long
- #define ld long double
- #define endl '\n'
- #define TIME 1.0*clock()/CLOCKS_PER_SEC
- #define pii pair < int , int >
- #define int ll
- //#pragma comment(linker, "/stack:200000000")
- //#pragma GCC optimize("Ofast")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- //#pragma GCC optimize("unroll-loops")
- using namespace std;
- const ll N = 100000 + 123;
- const ll mod = 1e9 + 7;
- const int rx[] = {-1, +1, 0, 0};
- const int ry[] = {0, 0, -1, +1};
- const ld eps = 0.00001;
- vector < int > g[N];
- int in[N], out[N], up[N][30], sz[N], h[N], timer;
- bool upper(int a, int b) {
- return(in[a] <= in[b] && out[a] >= out[b]);
- }
- void dfs(int v, int p) {
- in[v] = timer++;
- up[v][0] = p;
- for(int i = 1; i < 23; ++i) {
- up[v][i] = up[up[v][i - 1]][i - 1];
- }
- for(auto to : g[v]) {
- if(to == p)
- continue;
- dfs(to, v);
- }
- out[v] = timer++;
- }
- int lca(int a, int b) {
- if(upper(a, b))
- return a;
- if(upper(b, a))
- return b;
- for(int i = 22; i >= 0; --i) {
- if(!upper(up[a][i], b))
- a = up[a][i];
- }
- return up[a][0];
- }
- void calc(int v, int p, int cur) {
- sz[v] = 1;
- h[v] = cur;
- for(auto to : g[v]) {
- if(to == p)
- continue;
- calc(to, v, cur + 1);
- sz[v] += sz[to];
- }
- }
- int32_t main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- // srand(time(0));
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- // freopen("f.in", "r", stdin);
- // freopen("f.out", "w", stdout);
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- #endif
- int n;
- cin >> n;
- for(int i = 1; i < n; ++i) {
- int x, y;
- cin >> x >> y;
- --x;
- --y;
- g[x].pb(y);
- g[y].pb(x);
- }
- dfs(0, 0);
- calc(0, 0, 0);
- int m;
- cin >> m;
- //cout << m << endl;
- for(int i = 0; i < m; ++i) {
- int x, y;
- cin >> x >> y;
- --x;
- --y;
- int l = lca(x, y);
- // int d = h[l];
- if(x == y) {
- cout << n << endl;
- continue;
- }
- if((h[x] + h[y] - 2 * h[l]) % 2) {
- cout << 0 << endl;
- continue;
- }
- int res = 0;
- if(h[x] - h[l] == h[y] - h[l]) {
- res = 1;
- for(auto to : g[l]) {
- if(!upper(to, x) && !upper(to, y)) {
- res += sz[to];
- }
- }
- cout << res << endl;
- continue;
- }
- if(h[x] - h[l] != h[y] - h[l]) {
- int r = h[x] + h[y] - 2 * h[l];
- r /= 2;
- if(h[x] - h[l] < h[y] - h[l]) swap(x, y);
- int v = x;
- // cout << "r " << r << endl;
- // cout << "v " << v + 1 << " " << r << endl;
- for(int j = 22; j >= 0; --j) {
- if(r - (1ll << j) >= 0) {
- // cout << "hui";
- // cerr << j << endl;
- // cerr << "kek " << v << " " << j << " " << up[v][j] << endl;
- v = up[v][j];
- r -= (1ll << j);
- // cerr << j << " ";
- }
- }
- // cout << "! " << v + 1 << endl;
- res = 1;
- for(auto to : g[v]) {
- if(!upper(to, x) && !upper(to, y)) {
- res += sz[to];
- }
- }
- cout << res << endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement