题目链接：HDU5927-Auxiliary Set

题意：

对于一棵有n个节点，以1为根的树，树上节点分为重要节点和不重要节点，然后给出q个询问，每次询问给出不重要点的集合(大小为m)，问树上关键点的数量。

关键点的定义（满足一条即可）：

1. 关键点为重要节点。
2. 两个重要节点的LCA。

题解：

思维题，并不是想象中的数据结构/图论题。

因为一棵树有多组询问，对于每组询问，树的结构不会变。所以对于每个节点我们可以预处理出三个信息：

1. depth：深度
2. son：儿子的数量(即度数)
3. father

然后对于每组询问，我们可以先把集合中的点按深度排序，先把答案记为ans=n-m。

然后从最深的点开始处理，若当前点u的son>2，即表示该点有两个子树，并且没有比该点更深的非重要点，所以该点的儿子都是重要点，即两个重要点的LCA，ans+1。

若当前点u的son=0，即表示u不能为其父亲提供重要点，所以son[father[u]]-1。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005 + 5;
int T, n, q;
struct EDGE
{
    int v, nxt;
} edge[MAXN << 1];
int fir[MAXN], ecnt = 0;
void addedge(int u, int v)
{
    edge[ecnt].v = v;
    edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
}
int son[MAXN], fa[MAXN], depth[MAXN];
int so[MAXN], qu[MAXN];
bool cmp(int a, int b)
{
    return depth[a] > depth[b];
}
void dfs(int u, int F)
{
    fa[u] = F;
    for (int i = fir[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v;
        if (depth[v] || v == F)
            continue;
        depth[v] = depth[u] + 1;
        son[u]++;
        dfs(v, u);
    }
}
int main()
{
    scanf("%d", &T);
    int icase = 0;
    while (T--)
    {
        scanf("%d%d", &n, &q);
        ecnt = 0;
        for (int i = 1; i <= n; i++)
        {
            fir[i] = -1;
            son[i] = fa[i] = depth[i] = 0;
        }
        for (int i = 1; i <= n - 1; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            addedge(u, v), addedge(v, u);
        }
        depth[1] = 1;
        dfs(1, -1);
        printf("Case #%d:\n", ++icase);
        while (q--)
        {
            int m;
            scanf("%d", &m);
            for (int i = 1; i <= m; i++)
                scanf("%d", &qu[i]);
            int ans = n - m;
            sort(qu + 1, qu + 1 + m, cmp);
            for (int i = 1; i <= m; i++)
                so[qu[i]] = son[qu[i]];
            for (int i = 1; i <= m; i++)
                if (so[qu[i]] >= 2)
                    ans++;
                else if (so[qu[i]] == 0)
                    so[fa[qu[i]]]--;
            printf("%d\n", ans);
        }
    }
    return 0;
}