Solution
显然首都即树的重心。
考虑动态维护每棵树的重心，当连边
x
→
y
x→y
x→y 时 设连边之前，
x
,
y
x,y
x,y 所在树的重心为分别为
G
x
,
G
y
G_x,G_y
Gx,Gy，那么连边后新树的重心
z
z
z 一定在
G
x
→
G
y
G_x→G_y
Gx→Gy 的路径上。 记路径上
A
u
A_u
Au 和
B
u
B_u
Bu 是路径上某一点
u
u
u 的左右两个相邻节点，且满足
G
x
,
G
y
G_x,G_y
Gx,Gy 分别在子树
A
u
,
B
u
A_u,B_u
Au,Bu 中，显然
u
u
u 的最大子树只会是
A
u
,
B
u
A_u,B_u
Au,Bu 其中之一。
考虑在这条链上二分，二分到点
u
u
u 时，设树大小为
n
n
n，若
m
a
x
(
s
z
e
[
A
u
]
,
s
z
e
[
B
u
]
)
≤
n
/
2
max(sze[A_u],sze[B_u])≤n/2
max(sze[Au],sze[Bu])≤n/2，则
u
u
u 为重心。
但是题目要求找编号最小的重心，所以不论
u
u
u 是否为重心，都要继续二分下去，如果
s
z
e
[
A
u
]
>
s
z
e
[
B
u
]
sze[A_u]>sze[B_u]
sze[Au]>sze[Bu]，就往
A
u
A_u
Au 那边二分，否则往
B
u
B_u
Bu 那边二分。
问题转化为如何求
s
z
e
sze
sze。
类比
L
C
T
LCT
LCT，把
G
x
→
G
y
G_x→G_y
Gx→Gy 看作一条实路径，除此路径之外全是虚边，那么知道
G
x
→
A
u
，
B
u
→
G
y
G_x→A_u，B_u→G_y
Gx→Au，Bu→Gy 每个点的虚子树大小就好做了。
L
C
T
LCT
LCT 维护虚子树大小详见这里。
维护每棵树的重心可以用并查集，时间复杂度
O
(
n
log
n
)
O(n \log n)
O(nlogn)。
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;
}
