Advertisement
Guest User

Untitled

a guest
Apr 2nd, 2020
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.72 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. //#include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. #define pb push_back
  5. #define F first
  6. #define S second
  7. #define ll long long
  8. #define ull unsigned long long
  9. #define ld long double
  10. #define endl '\n'
  11. #define TIME 1.0*clock()/CLOCKS_PER_SEC
  12. #define pii pair < int , int >
  13. #define int ll
  14.  
  15. //#pragma comment(linker, "/stack:200000000")
  16. //#pragma GCC optimize("Ofast")
  17. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  18. //#pragma GCC optimize("unroll-loops")
  19.  
  20. using namespace std;
  21.  
  22. const ll N = 100000 + 123;
  23. const ll mod = 1e9 + 7;
  24. const int rx[] = {-1, +1, 0, 0};
  25. const int ry[] = {0, 0, -1, +1};
  26. const ld eps = 0.00001;
  27.  
  28. vector < int > g[N];
  29. int in[N], out[N], up[N][30], sz[N], h[N], timer;
  30.  
  31. bool upper(int a, int b) {
  32. return(in[a] <= in[b] && out[a] >= out[b]);
  33. }
  34.  
  35. void dfs(int v, int p) {
  36. in[v] = timer++;
  37. up[v][0] = p;
  38. for(int i = 1; i < 23; ++i) {
  39. up[v][i] = up[up[v][i - 1]][i - 1];
  40. }
  41. for(auto to : g[v]) {
  42. if(to == p)
  43. continue;
  44. dfs(to, v);
  45. }
  46. out[v] = timer++;
  47. }
  48.  
  49. int lca(int a, int b) {
  50. if(upper(a, b))
  51. return a;
  52. if(upper(b, a))
  53. return b;
  54. for(int i = 22; i >= 0; --i) {
  55. if(!upper(up[a][i], b))
  56. a = up[a][i];
  57. }
  58. return up[a][0];
  59. }
  60.  
  61. void calc(int v, int p, int cur) {
  62. sz[v] = 1;
  63. h[v] = cur;
  64. for(auto to : g[v]) {
  65. if(to == p)
  66. continue;
  67. calc(to, v, cur + 1);
  68. sz[v] += sz[to];
  69. }
  70. }
  71.  
  72. int32_t main() {
  73. ios_base::sync_with_stdio(0);
  74. cin.tie(0);
  75. cout.tie(0);
  76. // srand(time(0));
  77. #ifdef LOCAL
  78. freopen("input.txt", "r", stdin);
  79. freopen("output.txt", "w", stdout);
  80. #else
  81. // freopen("f.in", "r", stdin);
  82. // freopen("f.out", "w", stdout);
  83. // freopen("input.txt", "r", stdin);
  84. // freopen("output.txt", "w", stdout);
  85. #endif
  86. int n;
  87. cin >> n;
  88. for(int i = 1; i < n; ++i) {
  89. int x, y;
  90. cin >> x >> y;
  91. --x;
  92. --y;
  93. g[x].pb(y);
  94. g[y].pb(x);
  95. }
  96. dfs(0, 0);
  97. calc(0, 0, 0);
  98. int m;
  99. cin >> m;
  100. //cout << m << endl;
  101. for(int i = 0; i < m; ++i) {
  102. int x, y;
  103. cin >> x >> y;
  104. --x;
  105. --y;
  106. int l = lca(x, y);
  107. // int d = h[l];
  108. if(x == y) {
  109. cout << n << endl;
  110. continue;
  111. }
  112. if((h[x] + h[y] - 2 * h[l]) % 2) {
  113. cout << 0 << endl;
  114. continue;
  115. }
  116. int res = 0;
  117. if(h[x] - h[l] == h[y] - h[l]) {
  118. res = 1;
  119. for(auto to : g[l]) {
  120. if(!upper(to, x) && !upper(to, y)) {
  121. res += sz[to];
  122. }
  123. }
  124. cout << res << endl;
  125. continue;
  126. }
  127. if(h[x] - h[l] != h[y] - h[l]) {
  128. int r = h[x] + h[y] - 2 * h[l];
  129. r /= 2;
  130. if(h[x] - h[l] < h[y] - h[l]) swap(x, y);
  131. int v = x;
  132. // cout << "r " << r << endl;
  133. // cout << "v " << v + 1 << " " << r << endl;
  134. for(int j = 22; j >= 0; --j) {
  135. if(r - (1ll << j) >= 0) {
  136. // cout << "hui";
  137. // cerr << j << endl;
  138. // cerr << "kek " << v << " " << j << " " << up[v][j] << endl;
  139. v = up[v][j];
  140. r -= (1ll << j);
  141. // cerr << j << " ";
  142. }
  143. }
  144. // cout << "! " << v + 1 << endl;
  145. res = 1;
  146. for(auto to : g[v]) {
  147. if(!upper(to, x) && !upper(to, y)) {
  148. res += sz[to];
  149. }
  150. }
  151. cout << res << endl;
  152. }
  153. }
  154. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement