Address
Solution
-
显然首都即树的重心。
-
考虑动态维护每棵树的重心，当连边 \(x→y\) 时
设连边之前，\(x,y\) 所在树的重心为分别为 \(G_x,G_y\)，那么连边后新树的重心 \(z\) 一定在 \(G_x→G_y\) 的路径上。
记路径上 \(A_u\) 和 \(B_u\) 是路径上某一点 \(u\) 的左右两个相邻节点，且满足 \(G_x,G_y\) 分别在子树 \(A_u,B_u\) 中，显然 \(u\) 的最大子树只会是 \(A_u,B_u\) 其中之一。 -
考虑在这条链上二分，二分到点 \(u\) 时，设树大小为 \(n\)，若 \(max(sze[A_u],sze[B_u])≤n/2\)，则 \(u\) 为重心。
-
但是题目要求找编号最小的重心，所以不论 \(u\) 是否为重心，都要继续二分下去，如果 \(sze[A_u]>sze[B_u]\)，就往 \(A_u\) 那边二分，否则往 \(B_u\) 那边二分。
-
问题转化为如何求 \(sze\)。
-
类比 \(LCT\)，把 \(G_x→G_y\) 看作一条实路径，除此路径之外全是虚边，那么知道 \(G_x→A_u，B_u→G_y\) 每个点的虚子树大小就好做了。
-
\(LCT\) 维护虚子树大小详见这里。
-
维护每棵树的重心可以用并查集，时间复杂度 \(O(n \log n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
template <class t>
inline void read(t & res)
{
char ch;
while (ch = getchar(), !isdigit(ch));
res = ch ^ 48;
while (ch = getchar(), isdigit(ch))
res = res * 10 + (ch ^ 48);
}
const int e = 2e5 + 5;
int si[e], ans, q[e], s[e], n, lc[e], rc[e], fa[e], m, f[e];
bool rev[e];
inline int find(int x)
{
return f[x] == x ? x : f[x] = find(f[x]);
}
inline bool isroot(int x)
{
return !fa[x] || (lc[fa[x]] != x && rc[fa[x]] != x);
}
inline bool which(int x)
{
return rc[fa[x]] == x;
}
inline void pushdown(int x)
{
if (rev[x])
{
if (lc[x]) rev[lc[x]] ^= 1;
if (rc[x]) rev[rc[x]] ^= 1;
swap(lc[x], rc[x]);
rev[x] = 0;
}
}
inline void upt(int x)
{
s[x] = s[lc[x]] + s[rc[x]] + si[x] + 1;
}
inline void rotate(int x)
{
int y = fa[x], z = fa[y], b = (lc[y] == x ? rc[x] : lc[x]);
if (z && !isroot(y)) (lc[z] == y ? lc[z] : rc[z]) = x;
fa[x] = z; fa[y] = x;
if (b) fa[b] = y;
if (lc[y] == x)
{
lc[y] = b;
rc[x] = y;
}
else
{
rc[y] = b;
lc[x] = y;
}
upt(y);
upt(x);
}
inline void splay(int x)
{
int w = 1;
q[w = 1] = x;
for (int y = x; !isroot(y); y = fa[y]) q[++w] = fa[y];
for (int i = w; i >= 1; i--) pushdown(q[i]);
while (!isroot(x))
{
if (!isroot(fa[x]))
{
if (which(x) == which(fa[x])) rotate(fa[x]);
else rotate(x);
}
rotate(x);
}
}
inline void access(int x)
{
for (int y = 0; x; y = x, x = fa[x])
{
splay(x);
si[x] += s[rc[x]];
si[x] -= s[y];
rc[x] = y;
upt(x);
if (y) fa[y] = x;
}
}
inline void makeroot(int x)
{
access(x);
splay(x);
rev[x] ^= 1;
}
inline void link(int x, int y)
{
makeroot(x);
access(y);
splay(y);
fa[x] = y;
si[y] += s[x];
upt(y);
}
inline void split(int x, int y)
{
makeroot(y);
access(x);
splay(x);
}
inline int ask(int x)
{
int ls = 0, rs = 0, res = 1e8, mx = s[x] >> 1;
while (x)
{
pushdown(x);
int s1 = ls + s[lc[x]], s2 = rs + s[rc[x]];
if (max(s1, s2) <= mx) res = min(res, x);
if (s1 > s2) rs += si[x] + 1 + s[rc[x]], x = lc[x];
else ls += si[x] + 1 + s[lc[x]], x = rc[x];
}
splay(res);
return res;
}
inline char getc()
{
char ch;
while (ch = getchar(), !isalpha(ch));
char res = ch;
while (ch = getchar(), isalpha(ch));
return res;
}
int main()
{
int i, x, y;
read(n); read(m);
for (i = 1; i <= n; i++) s[i] = 1, f[i] = i, ans ^= i;
while (m--)
{
char op = getc();
if (op == 'X') printf("%d\n", ans);
else if (op == 'Q')
{
read(x);
printf("%d\n", find(x));
}
else
{
read(x); read(y); link(x, y);
x = find(x); y = find(y); split(x, y);
int z = ask(x); ans ^= x ^ y ^ z;
f[x] = f[y] = f[z] = z;
}
}
return 0;
}