[Luogu P4299] [BZOJ 3510]首都

洛谷传送门

BZOJ传送门

题目描述

在X$X$星球上有N$N$个国家，每个国家占据着X$X$星球的一座城市。由于国家之间是敌对关系，所以不同国家的两个城市是不会有公路相连的。

X$X$星球上战乱频发，如果A$A$国打败了B$B$国，那么B$B$国将永远从这个星球消失，而B$B$国的国土也将归A$A$国管辖。A$A$国国王为了加强统治，会在A$A$国和B$B$国之间修建一条公路，即选择原A$A$国的某个城市和B$B$国某个城市，修建一条连接这两座城市的公路。

同样为了便于统治自己的国家，国家的首都会选在某个使得其他城市到它距离之和最小的城市，这里的距离是指需要经过公路的条数，如果有多个这样的城市，编号最小的将成为首都。

现在告诉你发生在X$X$星球的战事，需要你处理一些关于国家首都的信息，具体地，有如下3种信息需要处理：

Axy$Axy$：表示某两个国家发生战乱，战胜国选择了x城市和y城市，在它们之间修建公路（保证其中城市一个在战胜国另一个在战败国）。
Qx$Qx$：询问当前编号为x的城市所在国家的首都。
Xor$Xor$：询问当前所有国家首都编号的异或和。

输入输出格式

输入格式：

第一行是整数N$N$，M$M$，表示城市数和需要处理的信息数。 接下来每行是一个信息，格式如题目描述（A$A$、Q$Q$、Xor$Xor$中的某一种）。

输出格式：

输出包含若干行，为处理Q$Q$和Xor$Xor$信息的结果。

输入输出样例

输入样例#1：

10 10 
Xor 
Q 1 
A 10 1 
A 1 4 
Q 4 
Q 10 
A 7 6 
Xor 
Q 7 
Xor

输出样例#1：

11 
1 
1 
1 
2 
6 
2 

说明

对于100$100$的数据，2≤N≤100000$2\le N\le 100000$，1≤M≤200000$1\le M\le 200000$。

解题分析

LCT动态维护树的重心。
容易证明当两棵树merge起来的时候， 重心肯定在两棵树原重心的最短路径上。而重心肯定是两边节点数量都不超过原来两棵树总点数的一半。
那么坑点来了：
1.split出来的链可能不仅仅有左儿子！显然access后只保证了原路径上经过的点在上面那个点的子树里， 并不保证都在两点之间。 如果只往左边跳， 结果是这样的：

我们画个图来模拟一下：

假设有两棵splay， 原重心分别为A$A$和b$b$。现在我们连上了C$C$到a$a$的一条边。
access时下面的splay先旋转：

然后是C点旋转， 最后成了这个样子：

然后我们splay(b)$splay(b)$，最后得到了这棵树：

显然原路径上的a$a$已经不在现在的最短路径中了， 所以需要考虑两边。

2.这种维护子树的题在link前需要先将上面的点splay上去！否则中间的点很多信息没有更新， 效果大概是这样的：

几千次询问后才出问题， 简直没法查错…
感觉之前学LCT的时候算法原理没有理解透彻， 导致出这么多基本错误。 以后还是应该多模拟多画图。

代码如下：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#define R register
#define IN inline
#define W while
#define gc getchar()
#define MX 500005
#define ls tree[now].son[0]
#define rs tree[now].son[1]
#define dad tree[now].fat
template <class T>
IN void in(T &x)
{
    x = 0; R char c = gc;
    W (!isdigit(c)) c = gc;
    W (isdigit(c))
    x = (x << 1) + (x << 3) + c - 48, c = gc;
}
struct Node
{
    int son[2], fat, sum, vir, mx;
    bool rev;
}tree[MX];
char buf[5];
int dot, q, Xor, top, big, sma;
int f[MX], sta[MX];
namespace BCJ
{
    void reset() {for (R int i = 1; i <= dot; ++i) f[i] = i;}
    int find(const int &now) {return f[now] == now ? f[now] : f[now] = find(f[now]);}
}
namespace LCT
{
    void reset() {for (R int i = 1; i <= dot; ++i) tree[i].sum = 1, Xor ^= i;}
    IN bool get(const int &now) {return tree[dad].son[1] == now;}
    IN bool nroot(const int &now) {return tree[dad].son[0] == now || tree[dad].son[1] == now;}
    IN void pushrev(const int &now) {std::swap(ls, rs), tree[now].rev ^= 1;}
    IN void pushup(const int &now) {tree[now].sum = 1 + tree[ls].sum + tree[rs].sum + tree[now].vir;}
    IN void pushdown(const int &now)
    {
        if(tree[now].rev)
        {
            if(ls) pushrev(ls);
            if(rs) pushrev(rs);
            tree[now].rev = false;
        }
    }
    IN void rotate(const int &now)
    {
        R bool dir = get(now);
        R int fa = dad, grand = tree[fa].fat;
        tree[fa].son[dir] = tree[now].son[dir ^ 1];
        tree[tree[now].son[dir ^ 1]].fat = fa;
        if(nroot(fa)) tree[grand].son[get(fa)] = now;
        tree[now].fat = grand;
        tree[now].son[dir ^ 1] = fa;
        tree[fa].fat = now;
        pushup(fa);
    }
    IN void splay(const int &now)
    {
        R int fa, grand, x = now; top = 0;
        sta[++top] = x;
        W (nroot(x)) x = tree[x].fat, sta[++top] = x;
        W (top) pushdown(sta[top--]);
        W (nroot(now))
        {
            fa = dad, grand = tree[fa].fat;
            if(nroot(fa)) rotate(get(now) == get(fa) ? fa : now);
            rotate(now);
        }
        pushup(now);
    }
    IN void access(R int now)
    {
        for (R int x = 0; now; x = now, now = dad)
        {
            splay(now);
            tree[now].vir += tree[rs].sum;
            rs = x;
            tree[now].vir -= tree[rs].sum;
            pushup(now);
        }
    }
    IN void makeroot(const int &now) {access(now), splay(now), pushrev(now);}
    IN void split(const int &x, const int &y) {makeroot(x), access(y), splay(y);}
    IN void link(const int &x, const int &y)
    {
        split(x, y);
        tree[x].fat = y, tree[y].vir += tree[x].sum, pushup(y);
    }
    IN void modify()
    {
        int ans = 99999999;
        long long pre = 0;
        split(sma, big);
        R int l = 0, r = 0, lsum = 0, rsum = 0, nowl, nowr, odd = tree[big].sum & 1, bd = tree[big].sum >> 1;
        for (R int now = big; now;)
        {
            pushdown(now);
            nowl = lsum + tree[l = ls].sum, nowr = rsum + tree[r = rs].sum;
            if(nowl <= bd && nowr <= bd)
            {
                if(odd) {ans = now; break;}//奇数大小时答案显然唯一， 直接退出
                if(ans > now) ans = now;//否则和之前的答案比较
            }
            if(nowl < nowr) lsum += tree[l].sum + tree[now].vir + 1, now = r;
            else rsum += tree[r].sum + tree[now].vir + 1, now = l;
            if(pre > 1ll * lsum * rsum) break;//说明两边的差在增大， 也就是说不可能会有更优解了， 直接退出
            else pre = 1ll * lsum * rsum;
        }
        splay(ans);
        f[big] = f[sma] = f[ans] = ans;
        Xor = Xor ^ ans ^ big ^ sma;
    }
}
int main(void)
{
    int a, b;
    in(dot), in(q);
    BCJ::reset(), LCT::reset();
    W (q--)
    {
        scanf("%s", buf);
        switch(buf[0])
        {
            case 'X':
            {
                printf("%d\n", Xor);
                break;
            }
            case 'Q':
            {
                in(a);
                printf("%d\n", BCJ::find(a));
                break;
            }
            case 'A':
            {
                in(a), in(b);
                sma = BCJ::find(a), big = BCJ::find(b);
                if(tree[sma].sum > tree[big].sum) std::swap(sma, big);
                LCT::link(a, b);
                LCT::modify();
            }
        }
    }
}