[原创]2016东北赛 && hdu 5927 Auxiliary Set [dfs序+BIT]【数据结构】

2017-06-05 16:38:47 Tabris_ 阅读数：299

博客爬取于2020-06-14 22:40:07
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72868717

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5927
————————————————————————————————————————————
Auxiliary Set

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

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 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
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

————————————————————————————————————————————
题意:

是有一颗有n个节点以11位根的树,有q次查询,每次查询给定一个集合,集合外的点是重要点,集合内的点是非重要点,如果非重要点是两个重要点的LCA,那么这个非重要点会变成重要点,问你重要点的个数.

解题思路:

开始看数据范围非常大,以为要O(M)查询,后来看哪个乱七八糟的数据范围,感觉带个log啥的,再加上剪剪枝也能做做看,…

首先对于一次查询,我们要知道了非重要点的个数m,那么集合外的重要点就是n-m

对于集合里面的重要点我们可以枚举,存在至少有两个节点在一个非重要点的不同儿子节点为根的子树上,那么这个非重要点就是两个重要点的LCA,就要++.;

那么考虑,会不会有非重要点是非重要点变成的重要点的LCA才计算的呢?,这种情况怎么处理,
其实很好想,如果非重要点变成重要点,那么这个非重要点的树一定有最开始就是重要点的节点,所以忽略这个情况就行了.

那么就是找节点子树中有没有重要点了,对于子树问题,想到dfs序,并用一个数组标记这个点是不是重要点,也就是看子树所包括的连续序列有没有被标记的,维护一个BIT,就能log计算了

然后注意一个剪枝,就是有两个儿子节点的树上有重要点,就可以break了.

附本题代码
————————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;
const int MOD = 10007;
const int N   = 100000+7;

# define abs(x)  ((x)>0?(x):-(x))

int read(){
    int x=0;char ch = getchar();
    while(ch<'0'||ch>'9') ch = getchar();
    while('0'<=ch&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x;
}

/*******************************/

vector<int>G[N];
int n,m,q;
int a[N],L[N],R[N],fa[N],cnt;
void dfs(int u,int f){
    L[u]=++cnt;fa[u]=f;
    int gz=G[u].size();
    for(int i=0,to;i<gz;i++){
        to=G[u][i];
        if(to==f) continue;
        dfs(to,u);
    }
    R[u]=cnt;
}

int sum[N];
# define lowbit(x) (x&-x)
void update(int i,int v){for(;i<=n;i+=lowbit(i))sum[i]+=v;}
int getSum(int i){int ans=0;for(;i;i-=lowbit(i))ans+=sum[i];return ans;}

int main(){
    int _=read(),kcase=0;
    while(_--){cnt=0;
        n=read(),q=read();
        update(1,1);
        for(int i=2,u,v;i<=n;i++){update(i,1);
            u=read(),v=read();
            G[u].push_back(v);
            G[v].push_back(u);
        }

        dfs(1,0);
        int ans;printf("Case #%d:\n",++kcase);
        while(q--){
            m=read();ans=n-m;
            for(int i=1;i<=m;i++) a[i]=read(),update(L[a[i]],0);

            for(int i=1;i<=m;i++){
                int gz=G[a[i]].size(),tot=0;
                for(int j=0,to;j<gz;j++){
                    to=G[a[i]][j];
                    if(to==fa[a[i]])continue;
                    if(getSum(R[to])-getSum(L[to]-1) > 0)tot++;
                }
                if(tot>=2) ans++;
            }
            printf("%d\n",ans);
            for(int i=1;i<=m;i++) update(L[a[i]],1);
        }

        for(int i=1;i<=n;i++)G[i].clear();
    }
    return 0;
}