构造只包含有用信息的新图，减少数据规模

虚树

概念

对于一棵树 $T$ ，构造一棵新树 $T’$ ，使得 $T’$ 中包含一些给定的节点和它们的 lca 且节点数尽量少，这个 $T’$ 就是虚树

明显， $T’$ 的点数少于 $T$ ，不妨假设 $n$ 为 $T$ 中节点个数，给定的关键节点集合为 $S$ ，那么对于每组 $S$ ，回答询问的时间复杂度可优化至 $O(\mid S \mid (\log n + \log \mid S \mid) + f( \mid S \mid))$ ，其中 $f(x)$ 表示对于一个 $x$ 个点的树回答询问的时间，另外，这只是一组点集，虚树可以处理多组点集，对于每组点集，可以证明，虚树的节点个数最多为 $2 \mid S \mid$ 个

构造

其实是有点暴力的

处理出 lca 和 dfn 序，然后对于每个点集 $S$ 按 dfn 序进行排序 ，同时维护一个栈，对于当前节点 $x$ ，记 $z = lca(x, stk[top])$ ：

1. 若 $z = stk[top]$ ，说明 $x$ 是 $stk[top]$ 的儿子，把 $x$ 入栈
2. 否则，不断弹出 $stk[top]$ 直到 $dep[stk[top]] \le dep[z]$ ，每次弹出连边 $stk[top - 1] \to stk[top]$ ；弹完后，若 $z \ne stk[top]$ ，把 $z$ 入栈，最后把 $x$ 入栈
3. 最后，当所有点的跟新结束后，还要弹出栈

具体实现时，有更简洁的打法（另外，为了简单，我们一般会把根先丢进栈）：

void ins(int x)
{
    if (!top) return void(stk[++top] = x);
    int z = lca(stk[top], x);
    for (; tp > 1 && dep[z] < dep[stk[top - 1]]; --top) add(stk[top - 1], stk[top]);
    if (dep[z] < dep[stk[top]]) add(z, stk[top--]);
    if (!top || stk[top] != z) stk[++top] = z;
    stk[++top] = x;
}

若用的是 $O(\log n)$ 的 lca ， $O(\mid S \mid \log \mid S \mid)$ 的排序，时间为 $O(\mid S \mid (\log n + \log \mid S \mid))$

例题

还是给一题

Kingdom and its Cities

直接每次询问建虚树，然后把关键节点的 $si$ 设为 $1$ ，其它为 $0$ ，在虚树上 dfs ，对于一个节点：

1. 若它的 $si \ne 0$ ，那么它的每一个 $si \ne 0$ 的儿子都不能和它联通，必须删掉（删掉该子树的任何一个点都一样）
2. 否则，令它的 $si$ 等于所有子树 $si$ 和，计算出来若它的 $si > 1$ ，显然把它删除就是最优的办法

一个要注意的是，邻接表和 $si$ 的清空不能 memset ，否则时间会退化，记 $K = \sum k$ 下面的代码时间为 $O(n \log n + K(\log n + \log K) + K)$

#include <bits/stdc++.h>
const int N = 1e5 + 100, D = 18;
int n, num = 0, q, k, ans;
int a[N], si[N];
struct Edge{ int ne, ver; } e[N << 1], ef[N << 1];
int h[N], idx = 0, hf[N], idf = 0;
int f[N][D], dep[N], dfn[N];
int stk[N], top;
void add(int x, int y){ e[idx] = {h[x], y}, h[x] = idx++; }
void adf(int x, int y){ ef[idf] = {hf[x], y}, hf[x] = idf++; }
void dfs1(int x, int fa)
{
    dfn[x] = ++num, f[x][0] = fa, dep[x] = dep[fa] + 1;
    for (int i = h[x]; ~i; i = e[i].ne) if (e[i].ver != fa) dfs1(e[i].ver, x);
}
int lca(int x, int y)
{
    if (dep[x] > dep[y]) std::swap(x, y);
    for (int i = D - 1; ~i; --i) if (dep[f[y][i]] >= dep[x]) y = f[y][i];
    if (x == y) return x;
    for (int i = D - 1; ~i; --i) if (f[y][i] != f[x][i]) y = f[y][i], x = f[x][i];
    return f[x][0];
}
void ins(int x)
{
    if (!top) return void(stk[++top] = x);
    int z = lca(x, stk[top]);
    for (; top > 1 && dep[z] < dep[stk[top - 1]]; --top) adf(stk[top - 1], stk[top]);
    if (dep[z] < dep[stk[top]]) adf(z, stk[top--]);
    if (!top || stk[top] != z) stk[++top] = z;
    stk[++top] = x;
}
void dfs2(int x)
{
    if (si[x])
        for (int i = hf[x], y; ~i; i = ef[i].ne)
        {
            dfs2(y = ef[i].ver);
            if (si[y]) si[y] = 0, ++ans;
        }
    else
    {
        for (int i = hf[x], y; ~i; i = ef[i].ne)
        {
            dfs2(y = ef[i].ver);
            si[x] += si[y];
            si[y] = 0;
        }
        if (si[x] > 1) si[x] = 0, ++ans;
    }
    hf[x] = -1;
}
void work()
{
    std::sort(a + 1, a + k + 1, [&](int x, int y){ return dfn[x] < dfn[y]; });
    top = ans = idf = 0;
    if (a[1] != 1) stk[++top] = 1; //根
    for (int i = 1; i <= k; ++i) ins(a[i]);
    for (; top > 1; --top) adf(stk[top - 1], stk[top]);
    dfs2(1), si[1] = 0;
    printf("%d\n", ans);
}
int main()
{
    memset(h, -1, sizeof h), memset(hf, -1, sizeof hf);
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; ++i)
    {
        scanf("%d %d", &u, &v);
        add(u, v), add(v, u);
    }
    dfs1(1, 0);
    for (int j = 1; j < D; ++j)
        for (int i = 1; i <= n; ++i) f[i][j] = f[f[i][j - 1]][j - 1];
    for (scanf("%d", &q); q--; )
    {
        scanf("%d", &k);
        for (int i = 1; i <= k; ++i)
        {
            scanf("%d", &a[i]);
            si[a[i]] = 1;
        }
        for (int i = 1; i <= k; ++i) if (si[f[a[i]][0]])
        {
            puts("-1");
            while(k) si[a[k--]] = 0;
            break;
        }
        if (!k) continue;
        work();
    }
    return 0;
}