1. 首页
2. DFS
3. 本页

HDU 5927 Auxiliary Set (DFS)

题目链接：点我~~

题意：给定一棵树，每次询问一个集合，问所有不在这个集合的点两两 LCA (可以相同)的并集大小。

思路：实际上就是对于每个被删掉的点，check 一下是不是除了一个子树之外的点都被删掉了。那么对于每个被删掉的点的连通块，从最高点开始 dfs 就行。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
const double eps=1e-5;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
#define Key_value ch[ch[root][1]][0]
const int MAXN = 100010;
const int MAXM = 10100;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline int read()
{
    int s=0;
    char ch=getchar();
    for(; ch<'0'||ch>'9'; ch=getchar());
    for(; ch>='0'&&ch<='9'; ch=getchar())s=s*10+ch-'0';
    return s;
}

struct node
{
    int u,v,next;
} edge[MAXN*2];

int head[MAXN],tol;
int sum[MAXN],fa[MAXN];

inline void init()
{
    memset(head,-1,sizeof(head));
    tol=0;
}
void addedge(int u,int v)
{
    edge[tol].v=v;
    edge[tol].next=head[u];
    head[u]=tol++;
    edge[tol].v=u;
    edge[tol].next=head[v];
    head[v]=tol++;
}

void dfs(int u,int f)
{
    fa[u]=f;
    sum[u]=0;
    for(int i=head[u]; ~i; i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==f)
            continue;
        dfs(v,u);
        sum[u]++;
    }
}

int a[MAXN];
int vis[MAXN];
vector<int >mp[MAXN];
int ans;

int dfs2(int u,int flag)
{
    if(vis[u]!=flag) return vis[u];
    int tot=0,res=0;
    int sz=mp[u].size();
    for(int i=0; i<sz; ++i)
    {
        int v=mp[u][i];
        if(dfs2(v,flag)>=1) res++;
        tot++;
    }
    if(sum[u]-tot+res>=2) return vis[u]=2;
    if(sum[u]-tot+res==1) return vis[u]=1;
    return vis[u]=0;
}

int main()
{
    int t;
    scanf("%d",&t);
    int casee=1;
    while(t--)
    {
        int n,q,m;
        scanf("%d%d",&n,&q);
        printf("Case #%d:\n",casee++);
        init();
        int u,v;
        for(int i=0; i<n-1; ++i)
        {
            u=read();
            v=read();
            addedge(u,v);
        }
        dfs(1,0);
        //memset(vis,0,sizeof(vis));
        while(q--)
        {
            scanf("%d",&m);
            int mk=(q+1)*-1;
            for(int i=1; i<=m; ++i)
            {
                a[i]=read();
                vis[a[i]]=mk;
                mp[a[i]].clear();
            }
            for(int i=1; i<=m; ++i)
            {
                if(vis[fa[a[i]]]==mk)
                    mp[fa[a[i]]].push_back(a[i]);
            }
            int ans=0;
            for(int i=1; i<=m; ++i)
            {
                if(dfs2(a[i],mk)==2)
                    ans++;
            }
            printf("%d\n",n-m+ans);
        }

    }

    return 0;
}