LCT维护边双连通分量、维护边权、维护子树信息
前言
算是LCT入门把hhh
希望能在去上自动机前发出去 QAQ
一点思考
- 为什么缩点后只需要改动access函数
首先，缩点是缩到了Splay的根节点，而splay操作不改变实链虚链，只在原splay上转转转，故对别的splay不会有影响，因此需要保证每次调用splay都是直接缩完点的点。这在操作中靠每次传入缩完点后的点保证，也靠access函数中每次跳缩完点后的点保证，splay函数本身不做修改
其次，所有函数中，只有access函数会跳到别人家的splay上去，并改变原splay结构，故需要改每次跳的真正的父节点
最后，剩余函数要么基于splay，要么基于access，故不用改
染色 - HYSBZ 2243
链接
https://cn.vjudge.net/problem/HYSBZ-2243
思路
还是原来那道染色，不过换用LCT做
由LCT中Splay的性质（中序遍历深度严格递增）可知，可对一个节点，维护其所维护的区间的最左端的颜色lcol（部分深度最浅的点）与最右端的颜色rcol（部分深度最深的点），再由此更新其维护的区间的颜色段数，核心代码就是下面这段啦
sum[x] = sum[lson] + sum[rson] + 1, lcol[x] = rcol[x] = col[x];
if(lson){
lcol[x] = lcol[lson];
if(rcol[lson] == col[x]) sum[x]--;
}
if(rson){
rcol[x] = rcol[rson];
if(lcol[rson] == col[x]) sum[x]--;
}
那么查询的时候只要split一下查就可以了
而修改还是用懒惰标记，此处注意！！做翻转的时候要同时交换lcol和rcol
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define lson ch[x][0]
#define rson ch[x][1]
using namespace std;
typedef long long ll;
const int N = 1e5 + 15;
const int inf = 0x3f3f3f3f;
inline int read(){
int x = 0;
char ch;
while((ch = getchar()) < '0' || ch > '9');
while('0' <= ch && ch <= '9'){
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}
inline void writeln(int x){
printf("%d\n", x);
}
struct LinkCutTree{
int fa[N], ch[N][2], sum[N], lzy[N], lzy_col[N];
int stk[N];
int col[N], lcol[N], rcol[N];
inline bool nRoot(int x){
return ch[fa[x]][0] == x || ch[fa[x]][1] == x;
}
void pushUp(int x){
sum[x] = sum[lson] + sum[rson] + 1, lcol[x] = rcol[x] = col[x];
if(lson){
lcol[x] = lcol[lson];
if(rcol[lson] == col[x]) sum[x]--;
}
if(rson){
rcol[x] = rcol[rson];
if(lcol[rson] == col[x]) sum[x]--;
}
}
void pushR(int x){
swap(lson, rson);
swap(lcol[x], rcol[x]);
lzy[x] ^= 1;
}
void updateColor(int x, int c){
sum[x] = lzy_col[x] = 1;
col[x] = lcol[x] = rcol[x] = c;
}
void pushDown(int x){
if(lzy[x]){
if(lson) pushR(lson);
if(rson) pushR(rson);
lzy[x] = 0;
}
if(lzy_col[x]){
if(lson) updateColor(lson, col[x]);
if(rson) updateColor(rson, col[x]);
lzy_col[x] = 0;
}
}
void rotate(int x){
int y = fa[x], z = fa[y];
int p = (ch[y][1] == x), w = ch[x][p^1];
if(nRoot(y)) ch[z][ch[z][1] == y] = x;
ch[x][p^1] = y, ch[y][p] = w;
if(w) fa[w] = y;
fa[y] = x, fa[x] = z;
pushUp(y);
}
void splay(int x){
int pstk = 0, y = x;
for(y = x; nRoot(y); y = fa[y]){
stk[++pstk] = y;
}
stk[++pstk] = y;
while(pstk) pushDown(stk[pstk--]);
while(nRoot(x)){
int y = fa[x], z = fa[y];
if(nRoot(y)) rotate((ch[y][0] == x) ^ (ch[z][0] == y) ? x : y);
rotate(x);
}
pushUp(x);
}
void access(int x){
for(int y = 0; x; y = x, x = fa[x]){
splay(x);
rson = y;
pushUp(x);
}
}
void makeRoot(int x){
access(x);
splay(x);
pushR(x);
}
int findRoot(int x){
access(x);
splay(x);
while(lson){
pushDown(x);
x = lson;
}
return x;
}
void split(int x, int y){
makeRoot(x);
access(y);
splay(y);
}
void link(int x, int y){
makeRoot(x);
if(findRoot(y) != x) fa[x] = y;
}
void cut(int x, int y){
makeRoot(x);
if(findRoot(y) == x && fa[x] == y && !rson){
fa[x] = ch[y][0] = 0;
pushUp(y);
}
}
};
LinkCutTree lct;
int main(){
int n = read(),m = read();
for(int i = 1; i <= n; i++){
lct.lcol[i] = lct.rcol[i] = lct.col[i] = read();
lct.sum[i] = 1;
}
for(int i = 1; i <= n - 1; i++){
int u = read(), v = read();
lct.link(u, v);
}
while(m--){
char op[2];
scanf("%s", op);
if(op[0] == 'Q'){
int u = read(), v = read();
lct.split(u, v);
writeln(lct.sum[v]);
}else{
int u = read(), v = read(), c = read();
lct.split(u, v);
lct.updateColor(v, c);
}
}
}
洛谷P2542 - [AHOI2005]航线规划
链接
https://www.luogu.org/problemnew/show/P2542
思路 —— LCT维护双连通分量
正向删边当然要改成 逆向添边，才好用并查集维护双连通分量
因此应该先把边读进来排个序，方便二分查找，然后再把操作读进来，对于操作中的删边操作，给读进来的边打个标记代表删除，再把剩余的边加入LCT中，并维护点的数量
在把剩余边加入LCT以及接下来逆向添边时，用并查集维护两点是否位于同一双连通中（缩点），那么在添边时，
若两点位于同一连通分量，则直接返回，否则会错！！！，
若不在连通分量中，而又位于同一棵树上，那么两点split的链就都位于同一双连通分量，DFS暴力合并到同一并查集进行缩点（缩到Splay的根节点），再取消这棵splay上所有点的ch，掉除了缩点后的点以外所有点的fa，
若不位于同一棵树上，那么就用普通的LCT连接即可
注意因为缩点了，因此需要修改access中的x = fa[x]，令其为x = fa[x] = ft[fa[x]]，这样才能真正跳到缩为一点的点上，添边操作与查询操作也需要找缩完的点
最后查询答案，两点split后桥的数量就是Splay中点数 - 1
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define lson ch[x][0]
#define rson ch[x][1]
using namespace std;
typedef long long ll;
const int N = 100000 + 15;
const int inf = 0x3f3f3f3f;
inline int read(){
int x = 0, tag = 1;
char ch;
while(((ch = getchar()) < '0' || ch > '9') && ch != '-');
if(ch == '-'){
tag = 0;
ch = getchar();
}
while('0' <= ch && ch <= '9'){
x = x * 10 + ch - '0';
ch = getchar();
}
return tag ? x : -x;
}
int ft[N];
int find(int x){
return ft[x] == x ? x : ft[x] = find(ft[x]);
}
void merge(int x, int y){
int p = find(x), q = find(y);
if(p != q) ft[q] = p;
}
struct LinkCutTree{
int fa[N], ch[N][2], sum[N], val[N], lzy[N];
int stk[N];
inline bool nRoot(int x){
return ch[fa[x]][0] == x || ch[fa[x]][1] == x;
}
void pushUp(int x){
sum[x] = sum[lson] + sum[rson] + 1;
}
void pushR(int x){
swap(lson, rson);
lzy[x] ^= 1;
}
void pushDown(int x){
if(lzy[x]){
if(lson) pushR(lson);
if(rson) pushR(rson);
lzy[x] = 0;
}
}
void rotate(int x){
int y = fa[x], z = fa[y];
int p = (ch[y][1] == x), w = ch[x][p^1];
if(nRoot(y)) ch[z][ch[z][1] == y] = x;
ch[x][p^1] = y, ch[y][p] = w;
if(w) fa[w] = y;
fa[y] = x, fa[x] = z;
pushUp(y);
}
void splay(int x){
int pstk = 0, y = x;
for(y = x; nRoot(y); y = fa[y]){
stk[++pstk] = y;
}
stk[++pstk] = y;
while(pstk) pushDown(stk[pstk--]);
while(nRoot(x)){
int y = fa[x], z = fa[y];
if(nRoot(y)) rotate((ch[y][0] == x) ^ (ch[z][0] == y) ? x : y);
rotate(x);
}
pushUp(x);
}
void access(int x){
for(int y = 0; x; y = x, x = fa[x] = find(fa[x])){
splay(x);
rson = y;
pushUp(x);
}
}
void makeRoot(int x){
access(x);
splay(x);
pushR(x);
}
int findRoot(int x){
access(x);
splay(x);
while(lson){
pushDown(x);
x = lson;
}
return x;
}
void split(int x, int y){
makeRoot(x);
access(y);
splay(y);
}
void dfs(int x, int u){
merge(x, u);
if(lson) dfs(lson, u);
if(rson) dfs(rson, u);
fa[x] = lson = rson = 0;
}
void link(int x, int y){
if(x == y) return;
makeRoot(x);
if(findRoot(y) != x){
fa[x] = y;
}else{
dfs(ch[y][0], y);
ch[y][0] = ch[y][1] = 0;
pushUp(y);
}
}
};
struct edge{
int u, v;
bool operator < (const edge& b) const{
if(u != b.u) return u < b.u;
else return v < b.v;
}
};
struct in{
int op, u, v;
};
LinkCutTree lct;
vector<in> input;
vector<int> ans;
edge e[N];
bool used[N];
inline void init(){
for(int i = 1; i < N; i++){
ft[i] = i;
}
}
int main(){
init();
int n = read(), m = read();
for(int i = 0; i < m; i++){
int u = read(), v = read();
if(u > v) swap(u, v);
e[i] = edge{u, v};
}
sort(e, e + m);
while(true){
int op = read();
if(op == -1) break;
int u = read(), v = read();
if(u > v) swap(u, v);
input.emplace_back(in{op, u, v});
if(op == 0){
int pos = lower_bound(e, e + m, edge{u, v}) - e;
used[pos] = true;
}
}
for(int i = 0; i < m; i++){
if(used[i]) continue;
lct.link(find(e[i].u), find(e[i].v));
}
for(vector<in>::reverse_iterator it = input.rbegin(); it != input.rend(); it++){
in& ele = *it;
int u = find(ele.u), v = find(ele.v);
if(ele.op == 1){
lct.split(u, v);
ans.emplace_back(lct.sum[v] - 1);
}else{
lct.link(u, v);
}
}
for(vector<int>::reverse_iterator it = ans.rbegin(); it != ans.rend(); it++){
printf("%d\n", *it);
}
}
洛谷P4180 -【模板】严格次小生成树[BJWC2010]
链接
https://www.luogu.org/problemnew/show/P4180
思路 —— LCT与生成树
正解并非LCT，只是用LCT可做，但是开了氧气优化
首先一个基本结论是 最小生成树与次小生成树之间只有一条边之差
因此按Kruskal的基本思路，排个序再添边，若不位于同一连通分量则直接link，否则尝试替换环中最大边或次大边（split操作），并更新差值delta，找到最小delta，再加上最小生成树的权值和就是答案了
在这里为什么要替换最大边或次大边呢，因为排个序后再添边，若遇到已经位于同一连通分量的，说明该边权值肯定不小于里面的，那么替换最大边是最划算的，但是可能等于，题目要求严格次小，所以当最大值与改边相同时，那么需要替换次小边，因此需要用LCT维护区间最大值和次大值
另外，findRoot较慢，改用并查集，然而不加氧气还是过不了QAQ
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define lson ch[x][0]
#define rson ch[x][1]
using namespace std;
typedef long long ll;
const int N = 3e5 + 15;
const int inf = 0x3f3f3f3f;
inline char get(void) {
static char buf[1000000], *p1 = buf, *p2 = buf;
if (p1 == p2) {
p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
if (p1 == p2) return EOF;
}
return *p1++;
}
inline void read(int& x) {
x = 0; static char c; bool minus = false;
for (; !(c >= '0' && c <= '9'); c = get()) if (c == '-') minus = true;
for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get()); if (minus) x = -x;
}
char WritellBuffer[1024];
inline void write(ll a,char end){
ll cnt=0,fu=1;
if(a<0){putchar('-');fu=-1;}
do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
putchar(end);
}
struct edge{
int u, v, w;
bool operator < (const edge& b) const{
return w < b.w;
}
};
edge e[N];
int ft[N];
inline void init(){
for(int i = 1; i < N; i++){
ft[i] = i;
}
}
int find(int x){
return ft[x] == x ? x : ft[x] = find(ft[x]);
}
void merge(int x, int y){
int p = find(x), q = find(y);
if(p != q) ft[q] = p;
}
struct LinkCutTree{
int fa[N], ch[N][2], mx1[N], mx2[N], val[N], lzy[N];
int stk[N];
inline bool nRoot(int x){
return ch[fa[x]][0] == x || ch[fa[x]][1] == x;
}
void pushUp(int x){
if(mx1[lson] > mx1[rson]){
mx1[x] = mx1[lson];
mx2[x] = max(mx2[lson], mx1[rson]);
}else if(mx1[lson] < mx1[rson]){
mx1[x] = mx1[rson];
mx2[x] = max(mx2[rson], mx1[lson]);
}else{
mx1[x] = mx1[lson];
mx2[x] = max(mx2[lson], mx2[rson]);
}
if(val[x] > mx1[x]){
mx2[x] = mx1[x];
mx1[x] = val[x];
}else if(val[x] != mx1[x] && val[x] > mx2[x]){
mx2[x] = val[x];
}
}
void pushR(int x){
swap(lson, rson);
lzy[x] ^= 1;
}
void pushDown(int x){
if(lzy[x]){
if(lson) pushR(lson);
if(rson) pushR(rson);
lzy[x] = 0;
}
}
void rotate(int x){
int y = fa[x], z = fa[y];
int p = (ch[y][1] == x), w = ch[x][p^1];
if(nRoot(y)) ch[z][ch[z][1] == y] = x;
ch[x][p^1] = y, ch[y][p] = w;
if(w) fa[w] = y;
fa[y] = x, fa[x] = z;
pushUp(y);
}
void splay(int x){
int pstk = 0, y = x;
for(y = x; nRoot(y); y = fa[y]){
stk[++pstk] = y;
}
stk[++pstk] = y;
while(pstk) pushDown(stk[pstk--]);
while(nRoot(x)){
int y = fa[x], z = fa[y];
if(nRoot(y)) rotate((ch[y][0] == x) ^ (ch[z][0] == y) ? x : y);
rotate(x);
}
pushUp(x);
}
void access(int x){
for(int y = 0; x; y = x, x = fa[x]){
splay(x);
rson = y;
pushUp(x);
}
}
void makeRoot(int x){
access(x);
splay(x);
pushR(x);
}
int findRoot(int x){
access(x);
splay(x);
while(lson){
pushDown(x);
x = lson;
}
return x;
}
void split(int x, int y){
makeRoot(x);
access(y);
splay(y);
}
};
LinkCutTree lct;
int main(){
int n, m;
read(n);
read(m);
init();
for(int i = 1; i <= m; i++){
read(e[i].u);
read(e[i].v);
read(e[i].w);
}
sort(e + 1, e + m + 1);
ll sum = 0;
int delta = inf;
int pp = n;
for(int i = 1; i <= m; i++){
int u = e[i].u, v = e[i].v, w = e[i].w;
if(find(u) == find(v)){
lct.split(u, v);
delta = min(delta, w - (w > lct.mx1[v] ? lct.mx1[v] : lct.mx2[v]));
}else{
lct.makeRoot(u);
lct.fa[u] = ++pp;
lct.fa[pp] = v;
lct.mx1[pp] = lct.val[pp] = w;
sum += w;
merge(pp, u);
merge(v, pp);
//printf("%d--\n", w);
}
}
write(sum + delta, '\n');
}
洛谷P4219 - [BJOI2014]大融合
链接
https://www.luogu.org/problemnew/show/P4219
思路 —— LCT维护子树大小
无外乎把(u, v)两点之间的边cut掉然后求个联通块的点数乘积，再连回去
但是split后求虚儿子的点数 + 1的乘积更好
对于解法1，记得求之前需要makeroot，因为维护的是子树点数，那么需要其为splay的根才能求得联通块点数
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define lson ch[x][0]
#define rson ch[x][1]
using namespace std;
typedef long long ll;
const int N = 1e5 + 15;
const int inf = 0x3f3f3f3f;
/*
inline char get(void) {
static char buf[1000000], *p1 = buf, *p2 = buf;
if (p1 == p2) {
p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
if (p1 == p2) return EOF;
}
return *p1++;
}
*/
inline int read() {
int x = 0; static char c; bool minus = false;
for (; !(c >= '0' && c <= '9'); c = getchar()) if (c == '-') minus = true;
for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = getchar()); if (minus) x = -x;
return x;
}
char WritellBuffer[1024];
template <typename T>
inline void write(T a,char end){
ll cnt=0,fu=1;
if(a<0){putchar('-');fu=-1;}
do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
if(end) putchar(end);
}
struct LinkCutTree{
int fa[N], ch[N][2], sum[N], val[N], lzy[N];
int stk[N];
int si[N];
inline bool nRoot(int x){
return ch[fa[x]][0] == x || ch[fa[x]][1] == x;
}
void pushUp(int x){
sum[x] = sum[lson] + sum[rson] + si[x] + 1;
}
void pushR(int x){
swap(lson, rson);
lzy[x] ^= 1;
}
void pushDown(int x){
if(lzy[x]){
if(lson) pushR(lson);
if(rson) pushR(rson);
lzy[x] = 0;
}
}
void rotate(int x){
int y = fa[x], z = fa[y];
int p = (ch[y][1] == x), w = ch[x][p^1];
if(nRoot(y)) ch[z][ch[z][1] == y] = x;
ch[x][p^1] = y, ch[y][p] = w;
if(w) fa[w] = y;
fa[y] = x, fa[x] = z;
pushUp(y);
}
void splay(int x){
int pstk = 0, y = x;
for(y = x; nRoot(y); y = fa[y]){
stk[++pstk] = y;
}
stk[++pstk] = y;
while(pstk) pushDown(stk[pstk--]);
while(nRoot(x)){
int y = fa[x], z = fa[y];
if(nRoot(y)) rotate((ch[y][0] == x) ^ (ch[z][0] == y) ? x : y);
rotate(x);
}
pushUp(x);
}
void access(int x){
for(int y = 0; x; y = x, x = fa[x]){
splay(x);
si[x] += sum[rson];
si[x] -= sum[y];
rson = y;
pushUp(x);
}
}
void makeRoot(int x){
access(x);
splay(x);
pushR(x);
}
int findRoot(int x){
access(x);
splay(x);
while(lson){
pushDown(x);
x = lson;
}
return x;
}
void split(int x, int y){
makeRoot(x);
access(y);
splay(y);
}
void link(int x, int y){
makeRoot(x);
if(findRoot(y) != x){
si[y] += sum[x];
fa[x] = y;
}
}
void cut(int x, int y){
makeRoot(x);
if(findRoot(y) == x && fa[x] == y && !rson){
fa[x] = ch[y][0] = 0;
pushUp(y);
}
}
};
LinkCutTree lct;
int main(){
int n = read(), m = read();
char op[2];
while(m--){
scanf("%s", op);
int x = read(), y = read();
if(op[0] == 'A'){
lct.link(x, y);
}else{
lct.split(x, y);
write((ll)(lct.si[x] + 1) * (lct.si[y] + 1), '\n');
}
}
}
