题解 CF613D 【Kingdom and its Cities】

考虑树形\(DP\)，设\(num_x\)记录的为当\(1\)为根时，以\(x\)为子树中重要城市的个数。

那么进行分类讨论：

① 当\(num_x≠0\)时，则需将其所有满足\(num_y≠0\)的儿子\(y\)删去。

② 当\(num_x=0\)时，若满足\(num_y≠0\)的儿子\(y\)个数\(cnt=1\)，则直接让\(num\)进行向上传递，若满足\(num_y≠0\)的儿子\(y\)个数\(cnt>1\)，则需删去\(x\)本身。

不合法的情况特判掉。

考虑到多次询问和树上点集的特性，考虑用虚树来优化\(DP\)。

多次建虚树时记得清空\(num\)，但不要用\(memset\)，无法保证复杂度，应记录虚树上的点，只清零这些点。

其他实现细节就看代码吧。

\(code:\)

#include<bits/stdc++.h>

#define maxn 200010

using namespace std;

template<typename T> inline void read(T &x)

{

	x=0;char c=getchar();bool flag=false;

	while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

	if(flag) x=-x;

}

int n,q,ans,tmp_cnt;

bool flag;

int query[maxn],tmp[maxn],num[maxn];

struct edge

{

    int to,nxt;

}e[maxn];

int head[maxn],edge_cnt;

void add(int from,int to)

{

    e[++edge_cnt]=(edge){to,head[from]};

    head[from]=edge_cnt;

}

int dfn_cnt;

int de[maxn],dfn[maxn],top_fa[maxn],fa[maxn],son[maxn],siz[maxn];

void dfs_son(int x,int fath)

{

    siz[x]=1;

    fa[x]=fath;

    de[x]=de[fath]+1;

    for(int i=head[x];i;i=e[i].nxt)

    {

        int y=e[i].to;

        if(y==fath) continue;

        dfs_son(y,x);

        siz[x]+=siz[y];

        if(siz[son[x]]<siz[y]) son[x]=y;

    }

}

void dfs_chain(int x,int tp)

{

    dfn[x]=++dfn_cnt,top_fa[x]=tp;

    if(son[x]) dfs_chain(son[x],tp);

    for(int i=head[x];i;i=e[i].nxt)

    {

        int y=e[i].to;

        if(dfn[y]) continue;

        dfs_chain(y,y);

    }

}

int lca(int x,int y)

{

    while(top_fa[x]!=top_fa[y])

    {

        if(de[top_fa[x]]<de[top_fa[y]]) swap(x,y);

        x=fa[top_fa[x]];

    }

    if(dfn[x]>dfn[y]) swap(x,y);

    return x;

}

bool cmp(const int &a,const int &b)

{

    return dfn[a]<dfn[b];

}

int st[maxn],top;

void insert(int x)

{

    if(x==1) return;

	if(top==1)

    {

        st[++top]=x;

        return;

    }

    int anc=lca(x,st[top]);

    if(anc==st[top])

    {

        st[++top]=x;

        return;

    }

    while(top>1&&dfn[anc]<=dfn[st[top-1]]) add(st[top-1],st[top]),top--,tmp[++tmp_cnt]=st[top];

    if(anc!=st[top]) add(anc,st[top]),st[top]=anc,tmp[++tmp_cnt]=st[top];

    st[++top]=x;

}

void dp(int x)

{

    int cnt=0,sum=0;

    for(int i=head[x];i;i=e[i].nxt)

    {

        int y=e[i].to;

        dp(y);

        if(num[x]&&num[y]) ans++;

        if(!num[x]&&num[y])

        {

            cnt++;

            sum+=num[y];

        }

    }

    if(!num[x])

    {

        if(cnt==1) num[x]+=sum;

        if(cnt>1) ans++;

    }

    head[x]=0;

}

void clear()

{

    edge_cnt=0;

    memset(head,0,sizeof(head));

}

int main()

{

	read(n);

    for(int i=1;i<n;++i)

    {

        int a,b;

        read(a),read(b);

        add(a,b),add(b,a);

    }

    dfs_son(1,0);

    dfs_chain(1,1);

    clear();

    read(q);

    while(q--)

    {

        int k;

        read(k);

        edge_cnt=tmp_cnt=flag=ans=0;

        for(int i=1;i<=k;++i)

        {

            read(query[i]);

            num[query[i]]++;

        }

        for(int i=1;i<=k;++i)

        {

            if(num[fa[query[i]]])

            {

                puts("-1");

                flag=true;

                break;

            }

        }

        if(flag)

        {

            for(int i=1;i<=k;++i) num[query[i]]=0;

            continue;

        }

        sort(query+1,query+k+1,cmp);

        st[top=1]=1,tmp[tmp_cnt=1]=1;

        for(int i=1;i<=k;++i) insert(query[i]);

        while(top) add(st[top-1],st[top]),top--,tmp[++tmp_cnt]=st[top];

        dp(1);

        for(int i=1;i<=tmp_cnt;++i) num[tmp[i]]=0;

        for(int i=1;i<=k;++i) num[query[i]]=0;

        printf("%d\n",ans);

    }

	return 0;

}

巴特西

题解 CF613D 【Kingdom and its Cities】

最新文章

热门文章