Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <unordered_map>
- #include <cstdio>
- #include <algorithm>
- using namespace std;
- using ll = long long;
- using ld = long double;
- const int N = 2e5 + 2;
- vector<int> adj[N];
- int n, q, m, k, a[N * 3];
- int now[N], ranks[N], par[19][N];
- unordered_map<int, int> s[N];
- void Read(){
- cin >> n >> q;
- for(int i = 1; i < n; ++i){
- int u, v;
- cin >> u >> v;
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- }
- void dfs(int v){
- now[v] = ++m;
- for(int i = 1; i <= 18; ++i)
- par[i][v] = par[i - 1][par[i - 1][v]];
- for(int i : adj[v])
- if(ranks[i] == 0){
- ranks[i] = ranks[v] + 1;
- par[0][i] = v;
- dfs(i);
- }
- }
- int find_lca(int u, int v){
- if(ranks[u] < ranks[v])
- swap(u, v);
- for(int i = 18; ~i; --i)
- if(ranks[par[i][u]] >= ranks[v])
- u = par[i][u];
- if(u == v)
- return u;
- for(int i = 18; ~i; --i)
- if(par[i][u] != par[i][v])
- u = par[i][u],
- v = par[i][v];
- return par[0][u];
- }
- int LCA(int u, int v){
- int &x = s[u][v];
- if(x != 0)
- return x;
- return x = find_lca(u, v);
- }
- void Solve(){
- cin >> k;
- for(int i = 1; i <= k; ++i)
- cin >> a[i];
- sort(a + 1, a + k + 1, [] (const int &x, const int &y){return now[x] < now[y];});
- a[k + 1] = a[1];
- int ans = 0;
- for(int i = 1; i <= k; ++i){
- int t = LCA(a[i], a[i + 1]);
- ans += ranks[a[i]] + ranks[a[i + 1]] - 2 * ranks[t];
- }
- cout << ans / 2 << "\n";
- }
- main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- Read();
- ranks[1] = 1; dfs(1);
- while(q--)
- Solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment