ZOJAuxiliary Set

Auxiliary Set

Time Limit: 9000/4500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1124    Accepted Submission(s): 351

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

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 uii and vi 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 ∑qi=1mi≤100000.

It is also guaranteed that the number of test cases in which n≥1000  or ∑qi=1mi≥1000 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

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

题意：给你一棵树（1为树根），树上有一些重要节点和一些不重要节点，划分一个集合，这个集合包括两种节点：
1、重要节点。
2、两个以上重要节点的公共父节点。求集合包含的节点个数。
给一个n个节点，q次询问，n-1个边，每次询问给出不重要节点。

解题思想：一开始看以为就是对树的搜索，判断不重要节点是不是重要节点的公共父节点，然而超时，之后看了题解才明白，仰慕菊苣啊。记录Dfs每个节点的父节点、深度、儿子的个数，然后按深度由大到小的顺序枚举m个不重要的节点。

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
#include <queue>
#include <vector>
using namespace std;
const int inf = 0x3f3f3f3f;
const int Max = 100100;
int n;
int a[Max], son[Max], vis[Max], deep[Max], fath[Max], ss[Max];
vector<int>ma[Max];

int Dfs(int key, int fa, int de)
{
    deep[key] = de;
    fath[key] = fa;
    vector<int>::iterator t;
    for(t = ma[key].begin(); t != ma[key].end(); t++)
    {
        if(!vis[*t])
        {
            vis[*t] = 1;
            Dfs(*t, key, de+1);
            son[key]++;
        }
    }
}
bool cmp(int a, int b)
{
    return deep[a]>deep[b];
}
int main()
{
    int K, j, i, k, u, v, q, m, sum;
    int h = 0;
    scanf("%d", &K);
    while(K--)
    {
        memset(vis, 0, sizeof vis);
        memset(son, 0, sizeof son);
        scanf("%d %d", &n, &q);
        for(i = 1; i <= n; i++)
        {
            ma[i].clear();
        }
        for(i = 1; i < n; i++)
        {
            scanf("%d %d", &u, &v);
            ma[u].push_back(v);
            ma[v].push_back(u);
        }
        vis[1] = 1;
        Dfs(1, 0, 1);
        /*for(i = 1; i <= n; i++)
        {
            printf("%d %d %d %d\n",i, fath[i], son[i], deep[i] );
        }*/
        printf("Case #%d:\n", ++h);
        while(q--)
        {
            scanf("%d", &m);
            for(i = 1; i <= m; i++)
            {
                scanf("%d", &a[i]);
            }
            sum = n - m;
            sort(a+1, a+m+1, cmp);
            for(i = 1; i <= m; i++)
                ss[a[i]] = son[a[i]];
            for(i = 1; i <= m; i++)
            {
                if(ss[a[i]] > 1)
                    sum++;
                else if(ss[a[i]] == 0)
                    ss[fath[a[i]]]--;
            }
            printf("%d\n", sum);
        }
    }
    return 0;
}