Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma comment(linker, "/stack:200000000")
- //#pragma GCC optimize("Ofast")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #include <bits/stdc++.h>
- using namespace std;
- #pragma GCC diagnostic ignored "-Wmissing-declarations"
- #define FINAL_OUT(x) {cout << (x) << '\n'; exit(0); }
- int const maxn = 100005;
- int const maxl = 19;
- vector<int> gr[maxn];
- int tin[maxn];
- int tout[maxn];
- int par[maxn][maxl];
- int curtime;
- void dfs(const int v = 1, const int p = 1)
- {
- tin[v] = ++curtime;
- par[v][0] = p;
- for(int i = 1; i < maxl; ++i)
- par[v][i] = par[par[v][i - 1]][i - 1];
- for(int ne : gr[v])
- if (ne != p)
- dfs(ne, v);
- tout[v] = ++curtime;
- }
- int lcacnt[maxn];
- vector<int> endv[maxn];
- inline bool upper(const int x, const int y)
- {
- return tin[x] <= tin[y] && tout[y] <= tout[x];
- }
- inline int lca(int x, const int y)
- {
- if (upper(x, y))
- return x;
- if (upper(y, x))
- return y;
- for(int i = maxl - 1; i >= 0; --i)
- if (!upper(par[x][i], y))
- x = par[x][i];
- return par[x][0];
- }
- long long ans = 0;
- int k;
- int curcnt = 0;
- set<int> solve(const int v = 1, const int p = 1)
- {
- curcnt += lcacnt[v];
- set<int> cur;
- for(int ne : gr[v])
- if (ne != p)
- {
- auto to = solve(ne, v);
- if (to.size() > cur.size())
- {
- to.insert(cur.begin(), cur.end());
- to.swap(cur);
- }
- else
- {
- cur.insert(to.begin(), to.end());
- }
- }
- cur.insert(endv[v].begin(), endv[v].end());
- ans += lcacnt[v] * 1LL * (curcnt - cur.size());
- return cur;
- }
- int main()
- {
- // freopen("in.txt","r", stdin);
- // freopen("out.txt", "w", stdout);
- ios_base::sync_with_stdio(false);
- int n;
- cin >> n;
- for(int i = 1; i < n; ++i)
- {
- int x,y;
- cin >> x >> y;
- gr[x].push_back(y);
- gr[y].push_back(x);
- }
- dfs();
- cin >> k;
- for(int i = 0; i < k; ++i)
- {
- int x,y;
- cin >> x >> y;
- endv[x].push_back(i);
- endv[y].push_back(i);
- ++lcacnt[lca(x,y)];
- }
- solve();
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment