题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5927
Time Limit: 9000/4500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Given a rooted tree with n vertices, some of the vertices are important.

An auxiliary set is a set containing vertices satisfying at least one of the two conditions：

  • It is an important vertex
  • It is the least common ancestor of two different important vertices.

You are given a tree with n vertices (1 is the root) and q queries.

Each query is a set of nodes which indicates the unimportant vertices in the tree. Answer the size (i.e. number of vertices) of the auxiliary set for each query.

Input

The first line contains only one integer T (T <= 1000), which indicates the number of test cases.

For each test case, the first line contains two integers n (1 <= n <= 100000), q (0 <= q <= 100000).
In the following n -1 lines, the i-th line contains two integers ui,vi (1<= ui,vi <= n) indicating there is an edge between u_ii and v_i in the tree.

In the next q lines, the i-th line first comes with an integer mi (1 <= mi <= 100000)indicating the number of vertices in the query set.Then comes with mi different integers, indicating the nodes in the query set.
It is guaranteed that .
It is also guaranteed that the number of test cases in which n <= 1000 or  is no more than 10.

Output

For each test case, first output one line "Case #x:", where x is the case number (starting from 1).

Then q lines follow, i-th line contains an integer indicating the size of the auxiliary set for each query. 

Sample Input

1
6 3
6 4
2 5
5 4
1 5
5 3
3 1 2 3
1 5
3 3 1 4

Sample Output

Case #1:
3
6
3

Hint


For the query {1，2, 3}:

  • node 4, 5, 6 are important nodes For the query {5}：
  • node 1，2, 3, 4, 6 are important nodes
  • node 5 is the lea of node 4 and node 3 For the query {3, 1，4}:
  • node 2, 5, 6 are important nodes

Problem solving report:

Description: 给出一棵有n个结点的树。然后有q次询问，每次询问给出k个点，告诉你这k个点是不重要的点。
需要求的是一个集合的大小，满足下面两个条件可以放入这个集合中:

  1. 重要的点；
  2. 如果某个不重要点是两个重要点的最小公共祖先，那么也放入这个集合中。

输出集合的大小。

Problem solving: DFS处理好每个点有多少个儿子。然后对于所有不重要的点，按照深度进行从大到小排序。从深度最大的开始检索。

如果当前节点的儿子数量大于等于2，那么当前点可以放入集合中。

如果当前点没有儿子，那么我们可以暂时删掉这个点(将其父亲的儿子节点的数量减1，如果他的父节点有两个儿子，一个为重要的，一个为不重要的，并且这个不重要的节点没有儿子节点了，那么这个父亲节点是不重要的点，虽然他有两个儿子，但是他只有一个重要的儿子)。按照这个规则检索就可以了。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct edge {
    int u, v;
}e[MAXN << 1];
int f[MAXN], p[MAXN], seq[MAXN], tmp[MAXN], dep[MAXN], pre[MAXN];
int cnt;
void init() {
    cnt = 0;
    memset(f, -1, sizeof(f));
    memset(seq, 0, sizeof(seq));
}
void Add(int u, int v) {
    e[++cnt] = {f[u], v};
    f[u] = cnt;
}
bool cmp(int a, int b) {
    return dep[a] > dep[b];
}
void DFS(int u, int fa, int de) {
    pre[u] = fa;
    dep[u] = de;
    for (int i = f[u]; ~i; i = e[i].u) {
        int v = e[i].v;
        if (v != fa) {
            seq[u]++;
            DFS(v, u, de + 1);
        }
    }
}
int main() {
    int t, n, q, kase = 0;
    scanf("%d", &t);
    while (t--) {
        init();
        scanf("%d%d", &n, &q);
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            Add(u, v), Add(v, u);
        }
        DFS(1, 0, 0);
        printf("Case #%d:\n", ++kase);
        while (q--) {
            int m, ans = 0;
            scanf("%d", &m);
            for (int i = 0; i < m; i++) {
                scanf("%d", &p[i]);
                tmp[p[i]] = seq[p[i]];
            }
            sort(p, p + m, cmp);
            for (int i = 0; i < m; i++) {
                if (tmp[p[i]] >= 2)
                    ans++;
                else if (!tmp[p[i]])
                    tmp[pre[p[i]]]--;
            }
            printf("%d\n", n - m + ans);
        }
    }
    return 0;
}