Guest User

Untitled

a guest
Mar 20th, 2018
189
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.23 KB | None | 0 0
  1. //#pragma comment(linker, "/stack:200000000")
  2. //#pragma GCC optimize("Ofast")
  3. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #pragma GCC diagnostic ignored "-Wmissing-declarations"
  7. #define FINAL_OUT(x) {cout << (x) << '\n'; exit(0); }
  8.  
  9.  
  10. int const maxn = 100005;
  11. int const maxl = 19;
  12. vector<int> gr[maxn];
  13.  
  14. int tin[maxn];
  15. int tout[maxn];
  16. int par[maxn][maxl];
  17.  
  18. int curtime;
  19.  
  20. void dfs(const int v = 1, const int p = 1)
  21. {
  22.     tin[v] = ++curtime;
  23.     par[v][0] = p;
  24.  
  25.     for(int i = 1; i < maxl; ++i)
  26.         par[v][i] = par[par[v][i - 1]][i - 1];
  27.     for(int ne : gr[v])
  28.     if (ne != p)
  29.         dfs(ne, v);
  30.     tout[v] = ++curtime;
  31. }
  32.  
  33. int lcacnt[maxn];
  34. vector<int> endv[maxn];
  35.  
  36. inline bool upper(const int x, const int y)
  37. {
  38.     return tin[x] <= tin[y] && tout[y] <= tout[x];
  39. }
  40.  
  41. inline int lca(int x, const int y)
  42. {
  43.     if (upper(x, y))
  44.         return x;
  45.     if (upper(y, x))
  46.         return y;
  47.  
  48.     for(int i = maxl - 1; i >= 0; --i)
  49.         if (!upper(par[x][i], y))
  50.             x = par[x][i];
  51.     return par[x][0];
  52. }
  53.  
  54.  
  55. long long ans = 0;
  56. int k;
  57.  
  58. int curcnt = 0;
  59.  
  60. set<int> solve(const int v = 1, const int p = 1)
  61. {
  62.     curcnt += lcacnt[v];
  63.     set<int> cur;
  64.     for(int ne : gr[v])
  65.     if (ne != p)
  66.     {
  67.         auto to = solve(ne, v);
  68.         if (to.size() > cur.size())
  69.         {
  70.             to.insert(cur.begin(), cur.end());
  71.             to.swap(cur);
  72.         }
  73.         else
  74.         {
  75.             cur.insert(to.begin(), to.end());
  76.         }
  77.     }
  78.     cur.insert(endv[v].begin(), endv[v].end());
  79.     ans += lcacnt[v] * 1LL * (curcnt - cur.size());
  80.     return cur;
  81. }
  82.  
  83. int main()
  84. {
  85. //    freopen("in.txt","r", stdin);
  86. //    freopen("out.txt", "w", stdout);
  87.     ios_base::sync_with_stdio(false);
  88.  
  89.     int n;
  90.     cin >> n;
  91.     for(int i = 1; i < n; ++i)
  92.     {
  93.         int x,y;
  94.         cin >> x >> y;
  95.         gr[x].push_back(y);
  96.         gr[y].push_back(x);
  97.     }
  98.     dfs();
  99.  
  100.     cin >> k;
  101.     for(int i = 0; i < k; ++i)
  102.     {
  103.         int x,y;
  104.         cin >> x >> y;
  105.         endv[x].push_back(i);
  106.         endv[y].push_back(i);
  107.         ++lcacnt[lca(x,y)];
  108.     }
  109.  
  110.     solve();
  111.     cout << ans << endl;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment