思路

这道题对初学虚树的人来讲简直就是噩梦…之前打了一个 30 分暴力未果，遂转向题解。知道了一个叫做虚树的东西，然后抄了一下午的题解才 AC。

我先来解释一下虚树这个数据结构(?)。在一棵书上，会有关键点集和非关键点集，在一些问题中我们只需要用到关键点之间的关系，而非关键点集便不在那么重要。这个时候我们可以建立一个虚树。

建立虚树的过程相当之繁琐，我在这里不在详细讲，可以使用单调栈和 LCA 算法以极高的效率搞定。详细见：https://oi-wiki.org/ds/virtual-tree/

以下为代码：

// P3233.cpp
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define pr pair<int, int>
using namespace std;
const int MX_N = 300020;
int head[MX_N], current;
struct edge
{
    int to, nxt;
} edges[MX_N << 1];
int fa[MX_N], stfa[20][MX_N], n, dep[MX_N], anses[MX_N], id[MX_N], dfn = 0, q, m;
int tmpx, tmpy, st[MX_N], top = 1, tsiz[MX_N];
pr mx[MX_N];
bool vis[MX_N];
void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}
void preprocess()
{
    for (int i = 1; i <= n; i++)
        stfa[0][i] = fa[i];
    for (int tim = 1; tim < 20; tim++)
        for (int u = 1; u <= n; u++)
            stfa[tim][u] = stfa[tim - 1][stfa[tim - 1][u]];
}
int jump(int u, int p)
{
    for (int i = 0; i <= 19; i++)
        if ((p >> i) & 1)
            u = stfa[i][u];
    return u;
}
int getLca(int a, int b)
{
    // b is deeper;
    if (dep[a] > dep[b])
        swap(a, b);
    b = jump(b, dep[b] - dep[a]);
    if (a == b)
        return a;
    for (int tim = 19; tim >= 0; tim--)
        if (stfa[tim][a] != stfa[tim][b])
            a = stfa[tim][a], b = stfa[tim][b];
    return fa[a];
}
void dfs_fa(int u)
{
    id[u] = ++dfn;
    tsiz[u] = 1;
    dep[u] = dep[fa[u]] + 1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (fa[u] != edges[i].to)
            fa[edges[i].to] = u, dfs_fa(edges[i].to), tsiz[u] += tsiz[edges[i].to];
}
bool compare(const int &a, const int &b) { return id[a] < id[b]; }
void dfs_1(int u)
{
    if (vis[u])
        mx[u] = make_pair(0, u);
    else
        mx[u] = make_pair(1e8, 0);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        dfs_1(to);
        pr tmp = mx[to];
        tmp.first = dep[mx[to].second] - dep[u];
        mx[u] = min(mx[u], tmp);
    }
}
void dfs_2(int u)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        pr p = mx[u];
        p.first += dep[edges[i].to] - dep[u];
        mx[edges[i].to] = min(mx[edges[i].to], p);
        dfs_2(edges[i].to);
    }
    anses[mx[u].second] = max(anses[mx[u].second], tsiz[u]);
}
void dfs_3(int u)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int x = mx[u].second, y = mx[edges[i].to].second;
        if (x != y)
        {
            int dist = dep[x] + dep[y] - (dep[getLca(x, y)] << 1);
            int z = jump(edges[i].to, (dist >> 1) - mx[edges[i].to].first);
            if (dist & 1)
                anses[x] -= tsiz[z];
            else
            {
                if (z != u && z != edges[i].to)
                    z = jump(edges[i].to, (dist >> 1) - mx[edges[i].to].first - (x < y));
                else if (z == u)
                    z = jump(edges[i].to, (dist >> 1) - mx[edges[i].to].first - 1);
                anses[x] -= tsiz[z];
            }
            if (edges[i].to != z)
                anses[y] += tsiz[z] - tsiz[edges[i].to];
        }
        dfs_3(edges[i].to);
    }
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
        scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy), addpath(tmpy, tmpx);
    dfs_fa(1);
    preprocess();
    scanf("%d", &q);
    while (q--)
    {
        current = 0;
        scanf("%d", &m);
        vector<int> harr, arrs;
        for (int i = 1; i <= m; i++)
            scanf("%d", &tmpx), vis[tmpx] = true, harr.push_back(tmpx), anses[tmpx] = 0, arrs.push_back(tmpx);
        sort(harr.begin(), harr.end(), compare);
        // start to build the virtual tree;
        // prep for the stack;
        st[top = 1] = 1, head[1] = -1;
        for (int i = 0; i < m; i++)
        {
            if (harr[i] == 1)
                continue;
            int curtpt = harr[i], lca = getLca(curtpt, st[top]);
            if (lca != st[top])
            {
                while (id[lca] < id[st[top - 1]])
                    addpath(st[top - 1], st[top]), top--;
                if (id[lca] > id[st[top - 1]])
                    head[lca] = -1, addpath(lca, st[top]), st[top] = lca;
                else
                    addpath(lca, st[top--]);
            }
            head[curtpt] = -1, st[++top] = curtpt;
        }
        for (int i = 1; i < top; i++)
            addpath(st[i], st[i + 1]);
        dfs_1(1), dfs_2(1), dfs_3(1);
        for (int i = 0; i < m; i++)
            printf("%d ", anses[arrs[i]]);
        printf("\n");
        for (int i = 0; i < m; i++)
            vis[arrs[i]] = false;
    }
    return 0;
}