洛谷4299首都（LCT维护动态重心+子树信息）

这个题目很有意思

QWQ

根据题目描述，我们可以知道，首都就是所谓的树的重心，那么我们假设每颗树的重心都是\(root\)的话，对于每次询问，我们只需要\(findroot(x)\)就可以。

那么如何处理\(link\)操作呢QWQ

这里是看了题解，我才知道是怎么做的

大致的思想就是：

！启发式合并！

首先，这里需要注意树的中心具有的两个性质：

1。以这个点为根，那么所有的子树（不算整个树自身）的大小都不超过整个树大小的一半。

2.假设两个联通块x和y进行合并，而且\(size(x)>size(y)\)，那么新的重心必然在连接原来两棵树重心的路径上。

那么我们对于一次\(link\)，首先要知道两棵树的重心的路径是什么样的，我们可以通过\(link+access\)，然后中序遍历来求出来

void dfs(int x,int lim)

{

	if (top>lim)

	{

		flag=true;

		return;

	}

	pushdown(x);

	if (ch[x][0]) dfs(ch[x][0],lim);

	if (flag) return;

	sta[++top]=x;

	if (flag) return;

	if (ch[x][1]) dfs(ch[x][1],lim);

	if (flag) return;

}

link(x,y);

access(x);

splay(ry);

dfs(ry,ymh);

一定记得\(dfs\)的时候要\(pushdown\)！！！

同时dfs的时候，如果路径上的点已经要比，较小的子树的size要大，就可以直接\(return\)，因为继续下去一定没有意义，就不可能会更新答案了。

然后把这条路径统计出来之后，我们只需要从\(root_大\)开始，看看当前的节点的子树大小*2，是不是大于总的\(size\)，如果大于，就移动，不然就\(break\)

int r = ry;

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

{

	splay(sta[i]);

	int now = xv[sta[i]]+1+sum[ch[sta[i]][1]];

	if (2*now>size || (2*now==size && sta[i]<=r)) r=sta[i];

	else break;

}

makeroot(r);

ans^=r;

大致就是这样，然后对于整体的询问，我们维护一个\(ans\)即可，每次合并之前先异或上两个\(root\)，然后最后再异或一下最后合并完的\(root\)

上代码

// luogu-judger-enable-o2

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<vector>

#include<queue>

#include<cmath>

#include<map>

#include<set>

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

int ch[maxn][3];

int fa[maxn],rev[maxn],st[maxn];

int n,m;

int sta[maxn];

int sum[maxn],xv[maxn];

int ans;

int son(int x)

{

    if (ch[fa[x]][0]==x) return 0;

    else return 1;

}

bool notroot(int x)

{

   return ch[fa[x]][0]==x || ch[fa[x]][1]==x;

}

void update(int x)

{

    sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+xv[x]+1;

}

void reverse(int x)

{

    swap(ch[x][0],ch[x][1]);

    rev[x]^=1;

}

void pushdown(int x)

{

    if (rev[x])

    {

        if (ch[x][0]) reverse(ch[x][0]);

        if (ch[x][1]) reverse(ch[x][1]);

        rev[x]=0;

    }

}

void rotate(int x)

{

    int y=fa[x],z=fa[y];

    int b=son(x),c=son(y);

    if (notroot(y)) ch[z][c]=x;

    fa[x]=z;

    ch[y][b]=ch[x][!b];

    fa[ch[x][!b]]=y;

    ch[x][!b]=y;

    fa[y]=x;

    update(y);

    update(x);

}

void splay(int x)

{

    int y=x,cnt=0;

    st[++cnt]=y;

    while (notroot(y)) y=fa[y],st[++cnt]=y;

    while (cnt) pushdown(st[cnt--]);

    while (notroot(x))

    {

        int y=fa[x],z=fa[y];

        int b=son(x),c=son(y);

        if (notroot(y))

        {

        	if (b==c) rotate(y);

        	else rotate(x);

        }

        rotate(x);

    }

    update(x);

}

void access(int x)

{

    for (int y=0;x;y=x,x=fa[x])

    {

        splay(x);

        xv[x]+=sum[ch[x][1]]-sum[y];

        ch[x][1]=y;

        update(x);

    }

}

void makeroot(int x)

{

    access(x);

    splay(x);

    reverse(x);

}

int findroot(int x)

{

    access(x);

    splay(x);

    while (ch[x][0])

    {

        pushdown(x);

        x=ch[x][0];

    }

    return x;

}

void split(int x,int y)

{

   makeroot(x);

   access(y);

   splay(y);

}

void link(int x,int y)

{

    split(x,y);

    if (findroot(y)!=x)

    {

      xv[y]+=sum[x];

      fa[x]=y;

      update(y);

    }

}

int q;

bool flag=false;

int top;

void dfs(int x,int lim)

{

    if (top>lim)

    {

        flag=true;

        return;

    }

    pushdown(x);

    if (ch[x][0]) dfs(ch[x][0],lim);

    if (flag) return;

    sta[++top]=x;

    if (flag) return;

    if (ch[x][1]) dfs(ch[x][1],lim);

    if (flag) return;

}

int main()

{

   n=read();q=read();

   for (int i=1;i<=n;i++) sum[i]=1,ans^=i;

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

   {

   	  char s[10];

   	  scanf("%s",s+1);

   	  if (s[1]=='X')

   	  {

   	  	cout<<ans<<"\n";

      }

      if (s[1]=='Q')

      {

      	int x=read();

      	cout<<findroot(x)<<"\n";

      }

      if (s[1]=='A')

      {

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

      	 flag=false;

      	 top=0;

      	 int rx=findroot(x);

      	 splay(rx);

      	 int ry=findroot(y);

      	 splay(ry);

         ans^=rx^ry;

      	 if (sum[rx]>sum[ry] || (sum[rx]==sum[ry] && rx<ry)) swap(x,y),swap(rx,ry);

      	 int ymh = sum[rx];int size = sum[rx]+sum[ry];

      	 link(x,y);

      	 access(x);

      	 splay(ry);

      	 dfs(ry,ymh);

      	 int r = ry;

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

      	 {

      	 	splay(sta[i]);

      	 	int now = xv[sta[i]]+1+sum[ch[sta[i]][1]];

      	 	if (2*now>size || (2*now==size && sta[i]<=r)) r=sta[i];

      	 	else break;

         }

         makeroot(r);

         ans^=r;

      }

   }

   return 0;

}

巴特西

洛谷4299首都（LCT维护动态重心+子树信息）

最新文章

热门文章