1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #define maxn 100005 7 #define maxm 400005 8 using namespace std; 9 10 int n,m,ans,vis[maxn],head,tot,now[maxn],prep[maxm],son_[maxm],fa[maxn],son[maxn][2],size[maxn],add[maxn],list[maxn],tail; 11 bool rev[maxn]; 12 13 bool which(int x){ 14 return son[fa[x]][1]==x; 15 } 16 17 bool isroot(int x){ 18 return son[fa[x]][0]!=x&&son[fa[x]][1]!=x; 19 } 20 21 void insert_(int x,int y){ 22 size[x]+=y,add[x]+=y; 23 } 24 25 void pushdown(int x){ 26 if (!x) return; 27 if (rev[x]){ 28 rev[x]^=1,swap(son[x][0],son[x][1]); 29 if (son[x][0]) rev[son[x][0]]^=1; 30 if (son[x][1]) rev[son[x][1]]^=1; 31 } 32 if (add[x]){ 33 if (son[x][0]) insert_(son[x][0],add[x]); 34 if (son[x][1]) insert_(son[x][1],add[x]); 35 add[x]=0; 36 } 37 } 38 39 void relax(int x){ 40 if (!isroot(x)) relax(fa[x]); 41 pushdown(x); 42 } 43 44 void rotata(int x){ 45 int y=fa[x],d=which(x),dd=which(y); 46 if (!isroot(y)) son[fa[y]][dd]=x; fa[x]=fa[y]; 47 fa[son[x][d^1]]=y,son[y][d]=son[x][d^1]; 48 fa[y]=x,son[x][d^1]=y; 49 } 50 51 void splay(int x){ 52 relax(x); 53 while (!isroot(x)){ 54 if (isroot(fa[x])) rotata(x); 55 else if (which(x)==which(fa[x])) rotata(fa[x]),rotata(x); 56 else rotata(x),rotata(x); 57 } 58 } 59 60 void access(int x){ 61 for (int p=0;x;x=fa[x]){ 62 splay(x); 63 son[x][1]=p; 64 p=x; 65 } 66 } 67 68 int succ(int x){ 69 splay(x); 70 int y=son[x][1]; 71 for (pushdown(y);son[y][0];y=son[y][0],pushdown(y)); 72 return y; 73 } 74 75 int find_root(int x){ 76 access(x); 77 splay(x); 78 while (son[x][0]) x=son[x][0]; 79 return x; 80 } 81 82 void insert(int x,int y){ 83 tot++,prep[tot]=now[x],now[x]=tot,son_[tot]=y; 84 } 85 86 void bfs(int x,int y){ 87 int t; 88 head=0,tail=1,list[1]=y,size[y]=1,fa[y]=son[y][0]=son[y][1]=0,vis[y]=m,add[y]=rev[y]=0; 89 while (head<tail){ 90 head++,t=list[head]; 91 for (int i=now[t],so=son_[i];i;i=prep[i],so=son_[i]){ 92 if (vis[so]!=m){ 93 vis[so]=m,size[so]=1,fa[so]=son[so][0]=son[so][1]=add[so]=rev[so]=0,fa[so]=t; 94 list[++tail]=so; 95 } 96 } 97 } 98 for (int i=tail;i>=1;i--){ 99 t=list[i]; 100 if (fa[t]) size[fa[t]]+=size[t]; 101 } 102 } 103 104 void make_root(int x){ 105 access(x); 106 splay(x); 107 rev[x]^=1; 108 } 109 110 void merge(int x,int y){ 111 int rx,ry,t; 112 rx=find_root(x),ry=find_root(y); 113 if (rx==ry) return; 114 if (size[rx]<size[ry]) swap(x,y),swap(rx,ry); 115 ans^=ry; 116 bfs(x,y),insert(x,y),insert(y,x),fa[y]=x; 117 access(x),splay(x),insert_(x,size[y]); 118 // access(ry),splay(rx),relax(ry); 119 access(ry); 120 for (;;){ 121 t=succ(rx); 122 if (!t){ 123 make_root(rx); 124 break; 125 } 126 if (size[t]*2>size[rx]||(size[t]*2==size[rx]&&t<rx)){ 127 // son[t][0]=0; 128 swap(size[t],size[rx]),size[rx]=size[t]-size[rx]; 129 ans^=rx,ans^=t,rx=t; 130 }else{ 131 make_root(rx); 132 break; 133 } 134 } 135 } 136 137 int main(){ 138 freopen("capital.in","r",stdin); 139 freopen("capital.out","w",stdout); 140 char st[5]; 141 int u,v; 142 memset(vis,-1,sizeof(vis)); 143 scanf("%d%d",&n,&m),ans=0; 144 tot=0,memset(now,0,sizeof(now)); 145 memset(rev,0,sizeof(rev)); 146 memset(size,0,sizeof(size)); 147 for (int i=1;i<=n;i++) add[i]=fa[i]=son[i][0]=son[i][1]=0,size[i]=1; 148 for (int i=1;i<=n;i++) ans^=i; 149 while (m--){ 150 scanf("%s",st+1); 151 if (st[1]=='X') printf("%d ",ans); 152 else if (st[1]=='Q') scanf("%d",&u),printf("%d ",find_root(u)); 153 else scanf("%d%d",&u,&v),merge(u,v); 154 } 155 return 0; 156 }
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3510
题意：一个森林，要求维护每棵树的重心（多个重心取编号最小的那个），支持三个操作：
1． 连接两个节点（保证两个节点不在同一棵树中）。
2． 询问某个节点所在树的重心。
3． 询问所有树的重心编号的异或和。
关于重心有几个性质：
- 以重心为根，任意一个子树的节点个数<=总结点数/2，否则重心可向该子树方向转移。
- 设树中节点x的权值为该点到树中每个点的距离之和，则重心的权值最小。
- 两个树合并为一颗新树后，新树的重心一定在原来的两个重心之间唯一的路径上。
做法：考虑用lct动态维护树的重心，以原树中的重心做为原树根，
由于只有合并操作（合并节点x和y，sizex>sizey），可以考虑启发式合并，即把节点数少的那棵树（y所在树）暴力重建（一次BFS），接到另一棵树（x所在树）上，节点y所在树上的信息可在bfs过程中维护好，节点x所在的树的size信息会有什么变化呢，我们发现节点x到原x树重心的路径上size[i]会加上y树的总结点数，这就是用lct的缘故。接下来我们考虑如何维护新树的重心，并作为新树的根呢？根据重心的性质3，我们考虑暴力转移重心，由于是启发式合并，据说复杂度可靠，我们将原来的两个重心的路径放到同一棵splay中来，从x树中重心开始暴力转移，如果节点p的后继节点q，若(sizeq*2>sizep)or（sizeq*2=sizep&&q<p），则将重心从p转移至q点，最后将make_root(新重心)，操作1得以解决。
对于操作2，用lct求该节点所在树的根即可，因为树根为重心。
对于操作3， 用ans维护即可，每次更新重心更新时更新ans。
Lct动态维护树的重心（Lct+启发式合并+暴力转移重心）。