Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <vector>
- #include <set>
- #include <map>
- #include <unordered_set>
- #include <unordered_map>
- #include <string>
- #include <cmath>
- #include <climits>
- #include <algorithm>
- #include <random>
- #include <iomanip>
- #include <ctime>
- #include <queue>
- #include <utility>
- #include <fstream>
- #include <bitset>
- typedef long long ll;
- typedef long double ld;
- using namespace std;
- #define all(x) (x).begin(),(x).end()
- #define sz(x) (int)x.size()
- int n, q, logn = 0, timer = 0, ki;
- vector<vector<int>> g, p, sparse;
- vector<int> tin, tout, sz_subtree, d, k, first, logs, order;
- vector<vector<pair<int, int>>> sz;
- void dfs(int v, int par) {
- tin[v] = timer;
- ++timer;
- p[v][0] = par;
- for (int i = 1; i < logn; ++i) {
- p[v][i] = p[p[v][i - 1]][i - 1];
- }
- for (int x : g[v]) {
- if (x != par) {
- dfs(x, v);
- }
- }
- tout[v] = timer;
- ++timer;
- }
- void size_dfs(int v, int par) {
- sz_subtree[v] = 1;
- for (int x : g[v]) {
- if (x != par) {
- size_dfs(x, v);
- sz_subtree[v] += sz_subtree[x];
- sz[x].push_back({ v, n - sz_subtree[x] });
- }
- }
- if (par != -1)
- sz[par].push_back({ v, sz_subtree[v] });
- }
- void depth_dfs(int v, int par, int _h) {
- d[v] = _h;
- order.push_back(v);
- for (int x : g[v]) {
- if (x != par) {
- depth_dfs(x, v, _h + 1);
- order.push_back(v);
- }
- }
- }
- int lca(int a, int b) {
- int left = first[a], right = first[b];
- if (left > right) swap(left, right);
- right += 1;
- int log = logs[right - left];
- int ans1 = sparse[log][left], ans2 = sparse[log][right - (1 << log)];
- return (d[ans1] < d[ans2] ? ans1 : ans2);
- }
- int dist(int v, int u) {
- return d[v] + d[u] - 2 * d[lca(u, v)];
- }
- void solve() {
- int ans = 0;
- int s = k[0];
- vector<int> x;
- for (int i = 1; i < ki; ++i) {
- int v = lca(s, k[i]), len = dist(s, k[i]);
- int need_len = len / 2 + 1;
- int xx;
- if (d[s] - d[v] >= need_len) {
- int ss = s;
- for (int l = logn - 1; l >= 0; --l) {
- int u = p[ss][l];
- if (d[s] - d[u] <= need_len)
- ss = u;
- }
- xx = ss;
- }
- else {
- need_len = (len - 1) / 2;
- int ss = k[i];
- for (int l = logn - 1; l >= 0; --l) {
- int u = p[ss][l];
- if (d[k[i]] - d[u] <= need_len)
- ss = u;
- }
- xx = ss;
- }
- x.push_back(xx);
- }
- for (int i = 0; i < sz(x); ++i) {
- for (int j = 0; j < sz(x); ++j) {
- if (x[i] == -1 || x[j] == -1 || i == j)
- continue;
- if (dist(s, x[i]) == dist(s, x[j]) + dist(x[j], x[i]))
- x[i] = -1;
- }
- }
- for (int i = 0; i < sz(x); ++i) {
- if (x[i] == -1)
- continue;
- int pr = -1;
- for (int pp = 0; pp < sz(sz[x[i]]); ++pp) {
- if (pr == -1 || dist(s, sz[x[i]][pp].first) < dist(s, sz[x[i]][pr].first))
- pr = pp;
- }
- ans += n - sz[x[i]][pr].second;
- }
- cout << n - ans << "\n";
- }
- void stupid() {
- vector<int> _used(n, 0);
- queue<int> qq;
- for (int i = 0; i < ki; ++i) {
- _used[k[i]] = (i ? -1 : 1);
- qq.push(k[i]);
- }
- while (!qq.empty()) {
- int s = qq.front();
- qq.pop();
- for (int x : g[s]) {
- if (!_used[x]) {
- _used[x] = _used[s];
- qq.push(x);
- }
- }
- }
- int ans = 0;
- for (int i = 0; i < n; ++i) {
- ans += (int)(_used[i] == 1);
- }
- cout << ans << "\n";
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- //reading
- {
- cin >> n >> q;
- while ((1 << logn) <= n)
- ++logn;
- logs.resize(n + 1);
- g.resize(n);
- tin.resize(n);
- tout.resize(n);
- sz_subtree.resize(n);
- d.resize(n);
- k.resize(n);
- p.resize(n, vector<int>(logn));
- sz.resize(n);
- first.resize(n, -1);
- for (int i = 0; i < n - 1; ++i) {
- int a, b;
- cin >> a >> b;
- --a; --b;
- g[a].push_back(b);
- g[b].push_back(a);
- }
- }
- dfs(0, 0);
- size_dfs(0, -1);
- depth_dfs(0, -1, 0);
- logs.resize(sz(order) + 1);
- logs[1] = 0;
- for (int i = 2; i < sz(order) + 1; ++i) {
- if ((1 << (logs[i - 1] + 1)) <= i) {
- logs[i] = logs[i - 1] + 1;
- }
- else {
- logs[i] = logs[i - 1];
- }
- }
- for (int i = 0; i < sz(order); ++i) {
- if (first[order[i]] == -1) {
- first[order[i]] = i;
- }
- }
- sparse.resize(logs[sz(order)] + 1, vector<int>(sz(order)));
- for (int i = 0; i < sz(order); ++i) {
- sparse[0][i] = order[i];
- }
- for (int i = 1; i <= logs[sz(order)]; ++i) {
- for (int j = 0; j + (1 << i) <= sz(order); ++j) {
- int ans1 = sparse[i - 1][j], ans2 = sparse[i - 1][j + (1 << (i - 1))];
- sparse[i][j] = (d[ans1] < d[ans2] ? ans1 : ans2);
- }
- }
- for (int _ = 0; _ < q; ++_) {
- cin >> ki;
- for (int i = 0; i < ki; ++i) {
- cin >> k[i];
- --k[i];
- }
- if (ki <= 20)
- solve();
- else
- stupid();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement