海亮01/15数据结构专题
T1
题意
在 X 星球上有 \(n\) 个国家，每个国家占据着 X 星球的一座城市，城市从 \(1\) 至 \(n\) 编号。由于国家之间是敌对关系，所以不同国家的两个城市是不会有公路相连的。
X 星球上战乱频发，如果 A 国打败了 B 国，那么 B 国将永远从这个星球消失，而 B 国的国土也将归 A 国管辖。A 国国王为了加强统治，会在 A 国和 B 国之间修建一条公路，即选择原 A 国的某个城市和 B 国某个城市，修建一条连接这两座城市的公路。
同样为了便于统治自己的国家，国家的首都会选在某个使得其他城市到它距离之和最小的城市，这里的距离是指需要经过公路的条数，如果有多个这样的城市，编号最小的将成为首都。
现在告诉你发生在 X 星球的战事，需要你处理一些关于国家首都的信息，具体地，有如下3种信息需要处理：
A x y：表示某两个国家发生战乱，战胜国选择了 \(x\) 城市和 \(y\) 城市，在它们之间修建公路（保证其中城市一个在战胜国另一个在战败国）。Q x：询问当前编号为 \(x\) 的城市所在国家的首都。Xor：询问当前所有国家首都编号的异或和。
题解
不会LCT的出门左转。
现在假设你已经会了LCT并且写过了模板。
然后考虑怎么维护一颗树的重心。
树的重心有很多优秀的性质，比如说我们即将用的这俩（摘自OI Wiki）：
- 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
- 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
先增加两个LCT节点的维护信息：
- \(siz\)：辅助树中，以自己为根的子树节点总数，加上自己的虚儿子的总数。
- \(si\)：自己虚儿子的 \(siz\) 总和。
然后就发现，对于连接操作，在连接两个节点之后，你可以 \(split\) 下原来的两棵树的重心，然后在 \(Splay\) 上二分答案。
维护重心直接用并查集维护即可。
总时间复杂度 \(O(n\log n\times 大常数)\)。
代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch =getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1e5 + 10;
struct LCT{
struct node{
int fa, ch[2], tag;
int siz, si;
node(int fa = 0,int c0 = 0,int c1 = 0,int tag = 0,int siz = 0,int si = 0
):fa(fa),tag(tag),siz(siz),si(si){ch[0] = c0;ch[1] = c1;}
}d[maxn];
#define C(p,x) d[p].ch[x]
#define FA(p) d[p].fa
void maintain(int p){d[p].siz = d[C(p,0)].siz + d[C(p,1)].siz + d[p].si + 1;}
int get(int p){return p == C(FA(p),0) ? 0 : (p == C(FA(p),1) ? 1 : -1);}
void connect(int p,int f,int chk){FA(p) = f;if(chk == 1 || chk == 0)C(f,chk) = p;}
void pushdown(int p){
if(d[p].tag){
swap(C(p,0),C(p,1));
if(C(p,0))d[C(p,0)].tag ^= 1;
if(C(p,1))d[C(p,1)].tag ^= 1;
d[p].tag = 0;
}
}
void pushdownall(int p){if(get(p) != -1)pushdownall(FA(p));pushdown(p);}
void rotate(int x){
int y = FA(x), z = FA(y), chkx = get(x), chky = get(y);
int u = chkx != -1 ? C(x,chkx ^ 1) : 0;
connect(u,y,chkx);connect(y,x,chkx ^ 1);connect(x,z,chky);
maintain(y);maintain(x);
}
void splay(int p){
pushdownall(p);
for(int f = FA(p);f = FA(p),get(p) != -1;rotate(p))
if(get(f) != -1)rotate(get(p) == get(f) ? f : p);
}
void access(int p){
int rs = 0;
while(p){
splay(p);
d[p].si += d[C(p,1) ].siz;
d[p].si -= d[C(p,1) = rs].siz;
rs = p;maintain(p);p = FA(p);
}
}
void makeroot(int p){
access(p);splay(p);
d[p].tag ^= 1;
}
void split(int x,int y){
makeroot(x);
access(y);splay(y);
}
int findroot(int p){
access(p);splay(p);
while(C(p,0)){pushdown(p);p = C(p,0);}
splay(p);return p;
}
void link(int x,int y){
makeroot(x);if(findroot(y) == x)return;
FA(x) = y; d[y].si += d[x].siz;maintain(y);
}
int getmid(int root,int siz){
int lsum = 0, rsum = 0;
int u = root;siz /= 2;
int rt = 0x3f3f3f3f;
while(u){
pushdown(u);
int L = lsum + d[C(u,0)].siz;
int R = rsum + d[C(u,1)].siz;
if(L <= siz && R <= siz){rt = min(rt,u);}
if(L < R){lsum = L + d[u].si + 1;u = C(u,1);}
else {rsum = R + d[u].si + 1;u = C(u,0);}
}
return rt;
}
}tree;
int fa[maxn];
int getf(int x){return fa[x] == x ? x : fa[x] = getf(fa[x]);}
int n, m;
int ans;
signed main(){
n = read(); m = read();char opt[10];int u, v;
for(int i = 1;i <= n;i++){ans ^= i;fa[i] = i;}
for(int i = 1;i <= m;i++){
scanf("%s",opt);
if(opt[0] == 'A'){
u = read(); v = read();
int fu = getf(u), fv = getf(v);
ans ^= fu ^ fv;tree.link(u, v);
tree.split(fu, fv);
int siz = tree.d[fv].siz;
int rt = tree.getmid(fv,siz);
ans ^= rt;tree.splay(rt);
fa[rt] = fa[fu] = fa[fv] = rt;
}
if(opt[0] == 'Q'){printf("%d\n",getf(read()));}
if(opt[0] == 'X'){printf("%d\n",ans);}
}
return 0;
}