洛谷4606 SDOI2018战略游戏（圆方树+虚树）

QWQ深受其害

当时在现场是真的绝望......

现在再重新来看这个题

QWQ

根据题目所说，我们可以发现，对于每一个集合中的节点，我们实际上就是要求两两路径上的割点的数目

考虑到又是关于点双的题目，而且在图上，我们并没有很好的办法去做。

这时候就要考虑建出来圆方树，然后我们对于圆方树的每个点，维护他到根的路径上的圆点个数

那么，我们该怎么求两两路径的割点总数呢（一看到数据范围，就想到虚树了啊）

冷静分析一下，发现真的直接把虚树中的点弄出来就是合法的，因为两两的路径一定会通过\(lca\)，而建出来虚树，正好只会保留有用的边。

那么我们对于虚树上的两个相连的点，他们的边权的就是两个点到根的圆点个数的差。

这里有一个关于虚树的

奇技淫巧

为了忽略\(1\)号节点对答案的影响，我们可以直接选择把所有关键点的\(lca\)放到虚树的栈里面当第一个元素，而不是1

最后对于一次询问，我们只需要求虚树的边权和即可（还需要特判根的问题）

// luogu-judger-enable-o2

#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 = 4e5+1e2;

const int maxm = 2*maxn;

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

int point1[maxn],nxt1[maxm],to1[maxm];

int cnt,cnt1;

int n,m;

int dfn[maxn],deep[maxn],low[maxn];

int f[maxn][20];

int st[maxn],tot,top;

int num;

int a[maxn],k;

int dnf[maxn],size[maxn];

void addedge1(int x,int y)

{

    nxt1[++cnt1]=point1[x];

    to1[cnt1]=y;

    point1[x]=cnt1;

}

void addedge(int x,int y)

{

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

    to[cnt]=y;

    point[x]=cnt;

}

void tarjan(int x,int fa)

{

    dfn[x]=low[x]=++tot;

    st[++top]=x;

    for (int i=point1[x];i;i=nxt1[i])

    {

       int p=to1[i];

       if (p==fa) continue;

       if (!dfn[p])

       {

          tarjan(p,x);

          low[x]=min(low[x],low[p]);

          if (low[p]>=dfn[x])

          {

           num++;

           addedge(num,x);

           addedge(x,num);

           do{

             addedge(num,st[top]);

              addedge(st[top],num);

              top--;

            }while (st[top+1]!=p);

          }

       }

       else low[x]=min(low[x],dfn[p]);

    }

}

int tmp;

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

{

    int now=0;

    if (x<=n) now++;

    deep[x]=dep;

    dnf[x]=++tmp;

    size[x]=size[fa]+now;

    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<=19;j++)

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

      {

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

     }

}

int go_up(int x,int d)

{

    for (int i=0;i<=19;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=19;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 dnf[a]<dnf[b];

}

struct xvtree{

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

    int val[maxm];

    int cnt;

    int s[maxn],top;

    int sum;

    void init()

    {

        cnt=0;

        sum=0;

    }

    void addedge(int x,int y,int w)

    {

     //cout<<x<<" ** "<<y<<" "<<w<<endl;

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

        to[cnt]=y;

        val[cnt]=w;

        point[x]=cnt;

    }

    void dfs(int x,int fa)

    {

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

        {

            int p = to[i];

            if (p==fa) continue;

            sum+=val[i];

            dfs(p,x);

        }

    }

    int solve()

    {

        init();

        top=1;

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

        int root=a[1];

        for (int i=2;i<=k;i++) root=lca(root,a[i]);

        s[top]=root;

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

        {

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

         if (l!=s[top])

         {

          while (top>1)

          {

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

           {

            addedge(s[top-1],s[top],size[s[top]]-size[s[top-1]]);//size表示他在圆方树上和根的路径上的圆点个数

            top--;

                    }

                    else

                    {

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

            {

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

             top--;

             break;

                        }

                        else

                        {

             addedge(l,s[top],size[s[top]]-size[l]);

             s[top]=l;

             break;

                        }

                    }

                }

            }

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

        }

        while (top>1)

        {

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

            top--;

        }

        dfs(root,0);

        if(root<=n) sum++;

        return sum;

    }

};

xvtree xv;

int t;

int main()

{

  t=read();

  while (t--)

  {

    tmp=0;tot=0;top=0;

    cnt=0;cnt1=0;

    xv.init();

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

    memset(point1,0,sizeof(point1));

    memset(f,0,sizeof(f));

    memset(dfn,0,sizeof(dfn));

    memset(low,0,sizeof(low));

    memset(dnf,0,sizeof(dnf));

    n=read(),m=read();

    num=n;

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

    {

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

     addedge1(x,y);

     addedge1(y,x);

     }

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

     {

      if (!dfn[i]) tarjan(i,0);

     }

     dfs(1,0,1);

     init();

     int q=read();

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

     {

      k=read();

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

         xv.init();

        cout<<xv.solve()-k<<"\n";

     }

  }

  return 0;

}

巴特西

洛谷4606 SDOI2018战略游戏（圆方树+虚树）

奇技淫巧

最新文章

热门文章