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

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

2017年06月05日 16:38:47 Tabris_ 阅读数:283

个人分类: hdu
==== 数据结构 ====


博客爬取于2019-04-18 17:16:12
以下为正文

版权声明:本文为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个节点以 1 位根的树,有q次查询,每次查询给定一个集合,集合外的点是 重要点 ,集合内的点是 非重要点 ,如果
非重要点 是两个 重要点 的LCA,那么这个 非重要点 会变成 重要点 ,问你重要点的个数.

解题思路:

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

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

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

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

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

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

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

#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;
}

 上一篇
<原>#  北信科1011 K. paulzhou和方程 [组合数学+差分序列]【数学】 <原># 北信科1011 K. paulzhou和方程 [组合数学+差分序列]【数学】
这是你自定义的文章摘要内容,如果这个属性有值,文章卡片摘要就显示这段文字,否则程序会自动截取文章的部分内容作为摘要
2017-06-06
下一篇 
<原>#  SUDT 3926 bLue的二叉树 [KMP or hash]【思维】 <原># SUDT 3926 bLue的二叉树 [KMP or hash]【思维】
这是你自定义的文章摘要内容,如果这个属性有值,文章卡片摘要就显示这段文字,否则程序会自动截取文章的部分内容作为摘要
2017-06-05
  目录