CF613D Kingdom and its Cities（虚树+贪心）

很休闲的一个题啊

其实一看到关于\(\sum k\)的限制，就知道是个虚树的题了

首先我们把虚树建出来，然后考虑怎么计算个数呢？

我们令\(f[x]\)表示以\(x\)的子树中，剩余了多少个还没有切断的关键点

首先，如果当前点是一个关键点的话，那么他所有的\(f[son]!=0\)的儿子都需要割掉，而且当前点的\(f[x]\)应该是1（因为只能删除非关键点）

如果当前点不是一个关键点的话，如果他有一个\(f[x]\)不为0的儿子，那么\(f[x]=f[son]\)，不然的话，就需要把这个点删掉（不能让他的儿子通过这个点联通起来），并且\(f[x]=0\)

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<map>

#include<set>

#define mk makr_pair

#define ll long long

using namespace std;

inline int read()

{

  int x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 2e5+1e2;

const int maxm = 2*maxn;

int point[maxn],nxt[maxm],to[maxm];

int cnt,n,m;

int dfn[maxn],deep[maxn],f[maxn][21];

int tag[maxn];

int tot,top,s[maxn];

int ans;

int size[maxn];

int dp[maxn];

int a[maxn],k;

bool ymh;

void addedge(int x,int y)

{

 nxt[++cnt]=point[x];

 to[cnt]=y;

    point[x]=cnt;

}

void dfs(int x,int fa,int dep)

{

 deep[x]=dep;

 dfn[x]=++tot;

 for (int i=point[x];i;i=nxt[i])

 {

  int p = to[i];

     if (p==fa) continue;

     f[p][0]=x;

     dfs(p,x,dep+1);

 }

}

void init()

{

 for (int j=1;j<=20;j++)

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

     f[i][j]=f[f[i][j-1]][j-1];

}

int go_up(int x,int d)

{

 for (int i=0;i<=20;i++)

   if ((1 << i) & d)

     x=f[x][i];

 return x;

}

int lca(int x,int y)

{

 if(deep[x]>deep[y]) x=go_up(x,deep[x]-deep[y]);

 else y =go_up(y,deep[y]-deep[x]);

 if (x==y) return x;

 for (int i=20;i>=0;i--)

 {

  if (f[x][i]!=f[y][i])

  {

   x=f[x][i];

   y=f[y][i];

  }

 }

 return f[x][0];

}

bool cmp(int a,int b)

{

   return dfn[a]<dfn[b];

}

void solve()

{

 cnt=0;

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

 top=1;

 s[top]=1;

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

 {

  int l = lca(s[top],a[i]);

  if (l!=s[top])

  {

   while (top>1)

   {

    if (dfn[s[top-1]]>dfn[l])

    {

     addedge(s[top-1],s[top]);

     top--;

    }

    else

    {

     if (dfn[s[top-1]]==dfn[l])

     {

      addedge(s[top-1],s[top]);

      top--;

      break;

     }

     else

     {

      addedge(l,s[top]);

      s[top]=l;

      break;

     }

    }

   }

  }

  if (s[top]!=a[i]) s[++top]=a[i];

 }

 while (top>1)

 {

  addedge(s[top-1],s[top]);

  top--;

 }

}

void dpp(int x,int flag)

{

 int yy =0;

  dp[x]=0;

  if (tag[x]==flag)

  {

    dp[x]=1;

    for (int &i=point[x];i;i=nxt[i])

    {

     int p = to[i];

     dpp(p,flag);

     if (tag[p]==flag && tag[x]==flag && deep[p]-deep[x]==1) ymh=0;

     if (dp[p]>0) ans++;

  }

  }

  else

  {

    dp[x]=0;

    for(int &i=point[x];i;i=nxt[i])

    {

     int p = to[i];

     dpp(p,flag);

     if (tag[p]==flag && tag[x]==flag && deep[p]-deep[x]==1) ymh=0;

     if (dp[p]>0) yy++,dp[x]+=dp[p];

  }

  if (yy>=2) dp[x]=0,ans++;

  }

}

int main()

{

  n=read();

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

  {

    int x=read(),y=read();

    addedge(x,y);

    addedge(y,x);

  }

  dfs(1,0,1);

  init();

  memset(point,0,sizeof(point));

  m=read();

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

  {

    k=read();

    ans=0;

    ymh=true;

    for (int j=1;j<=k;j++) a[j]=read(),tag[a[j]]=i;

    solve();

    dpp(1,i);

   // cout<<ymh<<endl;

    if (!ymh) ans=-1;

    cout<<ans<<"\n";

  }

  return 0;

}

巴特西

CF613D Kingdom and its Cities（虚树+贪心）

最新文章

热门文章