Guest User

Untitled

a guest
Jun 17th, 2020
945
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.00 KB | None | 0 0
  1. #include <vector>
  2. #include <set>
  3. #include <map>
  4. #include <queue>
  5. #include <stack>
  6. #include <deque>
  7. #include <bitset>
  8.  
  9. #include <iostream>
  10. #include <algorithm>
  11. #include <cmath>
  12. #include <iterator>
  13. #include <iomanip>
  14.  
  15. // #include <bits/stdc++.h>
  16. // #include <ext/pb_ds/tree_policy.hpp>
  17. // #include <ext/pb_ds/assoc_container.hpp>
  18.  
  19. using namespace std;
  20. // using namespace __gnu_pbds;
  21.  
  22. typedef long long ll;
  23. typedef long double ld;
  24. typedef pair<int, int> pi;
  25. typedef pair<ll,ll> pl;
  26. typedef pair<double,double> pd;
  27. typedef priority_queue<int, vector<int>, greater<int> > min_heap;
  28.  
  29. // template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
  30.  
  31. #define mp make_pair
  32. #define pb push_back
  33. #define f first
  34. #define s second
  35. #define lb lower_bound
  36. #define ub upper_bound
  37. #define all(x) x.begin(), x.end()
  38.  
  39. const double PI = 4*atan(1);
  40. const ll INF = 1e18;
  41. const int MX = 100001;
  42.  
  43. const int maxn = 1e5 + 5;
  44. vector<int> adj[maxn];
  45. const int ln = 16;
  46. int n, k;
  47. int anc[maxn][ln + 1], tin[maxn], tout[maxn], bit[maxn], depth[maxn];
  48. int timer = 1;
  49.  
  50. void dfs(int u, int p) {
  51. anc[u][0] = p;
  52. tin[u] = timer++;
  53. for (int i = 1; i <= ln; i++) {
  54. anc[u][i] = anc[anc[u][i - 1]][i - 1];
  55. }
  56. for (int v: adj[u]) {
  57. if (v != p) {
  58. depth[v] = depth[u] + 1;
  59. dfs(v, u);
  60. }
  61. }
  62. tout[u] = timer++;
  63. }
  64.  
  65. inline int lca(int u, int v) {
  66. if (depth[u] < depth[v]) swap(u, v);
  67. for (int i = ln; i >= 0; i--) {
  68. if ((depth[u] - (1 << i)) >= depth[v]) u = anc[u][i];
  69. }
  70. if (u == v) return u;
  71. for (int i = ln; i >= 0; i--) {
  72. if (anc[u][i] != anc[v][i]) {
  73. u = anc[u][i];
  74. v = anc[v][i];
  75. }
  76. }
  77. return anc[u][0];
  78. }
  79.  
  80. void update(int pos, int delta) {
  81. for (int i = pos; i <= timer; i += i & -i) {
  82. bit[i] += delta;
  83. }
  84. }
  85.  
  86. int get(int pos) {
  87. int res = 0;
  88. for (int i = pos; i > 0; i -= i & -i) {
  89. res += bit[i];
  90. }
  91. return res;
  92. }
  93.  
  94. int main() {
  95. ios::sync_with_stdio(0);
  96. cin.tie(0);
  97. freopen("maxflow.in", "r", stdin);
  98. freopen("maxflow.out", "w", stdout);
  99. cin >> n >> k;
  100. for (int i = 1; i < n; i++) {
  101. int u, v;
  102. cin >> u >> v;
  103. adj[u].pb(v);
  104. adj[v].pb(u);
  105. }
  106. dfs(1, 1);
  107. for (int i = 1; i <= k; i++) {
  108. int u, v;
  109. cin >> u >> v;
  110. if (tin[v] < tin[u]) swap(u, v);
  111. int l = lca(u, v);
  112. // cout << "u: " << u << ", v: " << v << ", l: " << l << "\n";
  113. update(tin[u], +1);
  114. update(tin[v], +1);
  115. update(tout[l], -1);
  116. update(tin[l], -1);
  117. int l2 = v;
  118. }
  119. int ans = get(1);
  120. for (int i = 2; i <= n; i++) {
  121. ans = max(ans, get(tout[i] - 1) - get(tin[i] - 1));
  122. }
  123. // for (int i = 1; i <= n; i++) {
  124. // cout << "i: " << i << ", i flow: " << get(tout[i] - 1) - get(tin[i] - 1) << "\n";
  125. // }
  126. cout << ans << "\n";
  127.  
  128. }
Advertisement
Add Comment
Please, Sign In to add comment