Advertisement
lalalalalalalaalalla

Untitled

Dec 18th, 2019
127
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.36 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <iomanip>
  5. #include <queue>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <unordered_map>
  9. #include <tuple>
  10. #include <iomanip>
  11. #include <stdio.h>
  12. #include <map>
  13. #include <bitset>
  14. #include <set>
  15. #include <stack>
  16. #include <queue>
  17. #include <unordered_set>
  18. #include <cassert>
  19. #include <stdlib.h>
  20. #include <time.h>
  21. #include <random>
  22.  
  23.  
  24. //#pragma GCC optimize("Ofast,no-stack-protector")
  25. //#pragma GCC target("sse,sse2,sse3,sse3,sse4")
  26. //#pragma GCC optimize("unroll-loops")
  27. //#pragma GCC optimize("fast-math")
  28. //#pragma GCC target("avx2")
  29. //#pragma GCC optimize("section-anchors")
  30. //#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
  31. //#pragma GCC optimize("vpt")
  32. //#pragma GCC optimize("rename-registers")
  33. //#pragma GCC optimize("move-loop-invariants")
  34. //#pragma GCC optimize("unswitch-loops")
  35. //#pragma GCC optimize("function-sections")
  36. //#pragma GCC optimize("data-sections")
  37.  
  38. #define int long long
  39. #define ll long long
  40. #define ull unsigned long long
  41. #define all(a) (a).begin(), (a).end()
  42. #define pii pair<int, int>
  43. #define pb push_back
  44. #define ld long double
  45.  
  46.  
  47. using namespace std;
  48.  
  49. //const int INF = 1e17;
  50. //const int mod = 2600000069;
  51. //const int p = 179;
  52. const int MAXN = 2e5 + 1;
  53. const int logn = 19;
  54.  
  55. int n;
  56. int here[MAXN], after[MAXN], tin[MAXN], tout[MAXN], up[MAXN][logn];
  57. vector<int> g[MAXN];
  58. int timer = 0;
  59.  
  60. void dfs(int v, int p) {
  61. up[v][0] = p;
  62. for (int i = 1; i < logn; i++) {
  63. up[v][i] = up[up[v][i - 1]][i - 1];
  64. }
  65. tin[v] = timer++;
  66. for (auto u : g[v]) {
  67. if (u != p) dfs(u, v);
  68. }
  69. tout[v] = timer;
  70. }
  71.  
  72. bool ancestor(int u, int v) {
  73. return tin[u] <= tin[v] && tout[u] >= tout[v];
  74. }
  75.  
  76. int ans = 0;
  77. void dfs1(int v, int p, int cur) {
  78. cur += here[v];
  79. // cout << v << " " << here[v] << "\n";
  80. // cout << v << " : " << cur << "\n";
  81. ans = max(cur, ans);
  82. for (auto u : g[v]) {
  83. if (u != p) {
  84. dfs1(u, v, cur);
  85. }
  86. }
  87. }
  88.  
  89. int lst(int v, int u) {
  90. if (ancestor(u, v)) {
  91. for (int i = logn - 1; i >= 0; i--) {
  92. if (!ancestor(up[v][i], u)) v = up[v][i];
  93. }
  94. return v;
  95. } else {
  96. for (int i = logn - 1; i >= 0; i--) {
  97. if (!ancestor(up[u][i], v)) u = up[u][i];
  98. }
  99. return u;
  100. }
  101. }
  102.  
  103. signed main() {
  104. ios_base::sync_with_stdio(0);
  105. cin.tie(0);
  106. cout.tie(0);
  107. cin >> n;
  108. int u, v;
  109. for (int i = 0; i < n - 1; i++) {
  110. cin >> u >> v;
  111. u--;v--;
  112. g[u].pb(v);
  113. g[v].pb(u);
  114. }
  115. dfs(0, 0);
  116. int m;
  117. cin >> m;
  118. for (int i = 0; i < m; i++) {
  119. cin >> u >> v;
  120. u--;v--;
  121. if (ancestor(u, v)) {
  122. // cout << "here1\n";
  123. here[0]++;
  124. int l = lst(u, v);
  125. here[l]--;
  126. here[v]++;
  127. } else if (ancestor(v, u)) {
  128. // cout << "here2\n";
  129. here[0]++;
  130. int l = lst(u, v);
  131. here[l]--;
  132. here[u]++;
  133. } else {
  134. here[u]++;
  135. here[v]++;
  136. }
  137. }
  138. // for (int i = 0; i < n; i++) {
  139. // cout << i << " : " << here[i] << " " << after[i] << "\n";
  140. // }
  141. // cout << "\n";
  142. dfs1(0, 0, 0);
  143. cout << ans;
  144. }
  145. /*
  146. 4
  147. 1 2
  148. 1 3
  149. 1 4
  150. 2
  151. 1 4
  152. 2 3
  153. -> 2
  154. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement