Kalorona

LCT 的一类题目

LCT 简述

LCT (Link Cut Tree) 是一种维护树链的灵活的数据结构。与线段树不同的是，LCT 一般使用 Splay 这种非常优雅、灵活的数据结构来维护树链。因为 LCT 支持动态增边、删边，所以很多题目就可以打破一些限制进行求解。

LCT 的主要操作：

  • Pushup,Pushdown 操作：数据结构基本操作
  • Rotate 操作：这个是 Splay 的旋转操作
  • Splay 操作：这个是 Splay 的伸展操作
  • Access 操作：将点\(p\)到 Splay 根的链打通
  • MakeRoot 操作：将某个点作为树根
  • Find 操作：找到当前 Splay 的根
  • Link 操作：加边
  • Cut 操作：删边
  • Split 操作：提取一链

最小生成树中 LCT 的经典模型

LCT 的很多题目的模型基本都来源于 LCT 做最小生成树的方法。LCT 做最小生成树的方法与 Kruskal 非常的相似（虽然有很多不必要的步骤，但是这是经典模型的一部分），我在这里将进行介绍。

初始化好了一个 LCT 之后，我们把边从小到大进行排序，然后我们将条边视为一个点加上两条边，且点权即为边权：

 

考虑后面发现有环时（同一连通块时），进行检查：如果当前 LCT 中存在比当前大的边（当然排了序之后并不会出现这种情况），直接 Cut 操作掉这一点两边。

差值最小生成树

这个其实也运用到了 LCT 求最小生成树的思想。把边从小到大排序之后，枚举边的上界，并且在没有环的情况下进行 Link 操作；如果有环，那么删除当前连通块中最小的边，贪心地保持差值最小。当整棵树完整的时候（存在 n – 1 条边时），对答案进行更新即可。

// P4234.cpp
#include <bits/stdc++.h>
#define lson (ch[p][0])
#define rson (ch[p][1])

using namespace std;

const int MAX_N = 50000 + 5, MAX_E = 200005;
const long long INF = (1LL << 62);

struct edge
{
    int src, dst, weight, id;
    bool operator<(const edge &target) const { return weight < target.weight; }
} edges[MAX_E << 1];

int n, m, fa[MAX_E << 1], idx[MAX_E << 1], ch[MAX_E << 1][2];
bool tag[MAX_E << 1], book[MAX_E << 1];

int check(int x) { return ch[fa[x]][1] == x; }

bool isRoot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }

inline void update(int p)
{
    idx[p] = p;
    if (idx[lson] > n && (idx[p] <= n || idx[p] > idx[lson]))
        idx[p] = idx[lson];
    if (idx[rson] > n && (idx[p] <= n || idx[p] > idx[rson]))
        idx[p] = idx[rson];
}

inline void pushdown(int p)
{
    if (tag[p])
    {
        if (lson)
            tag[lson] ^= 1, swap(ch[lson][0], ch[lson][1]);
        if (rson)
            tag[rson] ^= 1, swap(ch[rson][0], ch[rson][1]);
        tag[p] = 0;
    }
}

inline void rotate(int x)
{
    int y = fa[x], z = fa[y], dir = check(x), w = ch[x][dir ^ 1];
    fa[x] = z;
    if (!isRoot(y))
        ch[z][check(y)] = x;
    ch[y][dir] = w, fa[w] = y;
    ch[x][dir ^ 1] = y, fa[y] = x;
    update(y), update(x), update(z);
}

inline void jump(int x)
{
    if (!isRoot(x))
        jump(fa[x]);
    pushdown(x);
}

inline void splay(int p)
{
    jump(p);
    for (int fat = fa[p]; fat = fa[p], !isRoot(p); rotate(p))
        if (!isRoot(fat))
            rotate(check(fat) == check(p) ? fat : p);
}

inline void access(int p)
{
    for (int fat = 0; p != 0; fat = p, p = fa[p])
        splay(p), ch[p][1] = fat, update(p);
}

inline void makeRoot(int p)
{
    access(p), splay(p);
    swap(lson, rson), tag[p] ^= 1;
}

inline int find(int p)
{
    access(p), splay(p), pushdown(p);
    while (lson)
        pushdown(p = lson);
    splay(p);
    return p;
}

inline void link(int x, int y)
{
    makeRoot(x);
    fa[x] = y;
}

inline void split(int x, int y) { makeRoot(x), access(y), splay(y); }

inline bool judge(int x, int y)
{
    makeRoot(x);
    return (find(y) == x);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y, w; i <= m; i++)
        scanf("%d%d%d", &x, &y, &w), edges[i].src = x, edges[i].dst = y, edges[i].weight = w;
    sort(edges + 1, edges + 1 + m);

    for (int i = 1; i <= m; i++)
        edges[i].id = n + i;

    long long answer = INF, lbound = 1, block_num = 0;
    for (int i = 1; i <= m; i++)
    {
        if (edges[i].src == edges[i].dst)
        {
            book[i] = true;
            continue;
        }

        if (!judge(edges[i].src, edges[i].dst))
            link(edges[i].src, edges[i].id), link(edges[i].id, edges[i].dst), block_num++;
        else
        {
            split(edges[i].src, edges[i].dst);
            int now = idx[edges[i].dst];
            book[now - n] = true, splay(now);
            fa[ch[now][0]] = fa[ch[now][1]] = 0;
            link(edges[i].src, edges[i].id), link(edges[i].id, edges[i].dst);
        }
        while (book[lbound] && lbound <= i)
            lbound++;
        if (block_num >= n - 1)
            answer = min(answer, 1LL * edges[i].weight - 1LL * edges[lbound].weight);
    }
    printf("%lld", answer);
    return 0;
}

例题：P2387 [NOI2014]魔法森林

这道题也是用 LCT 维护最小生成树的思路来求解的。考虑先按照\(a_i\)进行排序，然后固定上界\(a_i\)求\(b_i\)最小生成树即可。

// P2387.cpp
#include <bits/stdc++.h>
#define lson ch[p][0]
#define rson ch[p][1]

using namespace std;

const int MAX_N = 2e5 + 200;

struct edge
{
    int src, dst, ai, bi;
    bool operator<(const edge &edg) const { return ai < edg.ai || (ai == edg.ai && bi < edg.bi); }
} edges[MAX_N];

int n, m, ch[MAX_N][2], fa[MAX_N], idx[MAX_N], val[MAX_N], tag[MAX_N];

inline bool isRoot(int p) { return ch[fa[p]][0] != p && ch[fa[p]][1] != p; }

inline int check(int p) { return ch[fa[p]][1] == p; }

inline void pushup(int p)
{
    idx[p] = p;
    if (lson && val[idx[lson]] > val[idx[p]])
        idx[p] = idx[lson];
    if (rson && val[idx[rson]] > val[idx[p]])
        idx[p] = idx[rson];
}

inline void pushdown(int p)
{
    if (tag[p])
    {
        tag[p] = 0;
        if (lson)
            tag[lson] ^= 1, swap(ch[lson][0], ch[lson][1]);
        if (rson)
            tag[rson] ^= 1, swap(ch[rson][0], ch[rson][1]);
    }
}

inline void rotate(int p)
{
    int y = fa[p], z = fa[y], dir = check(p), w = ch[p][dir ^ 1];
    fa[p] = z;
    if (!isRoot(y))
        ch[z][check(y)] = p;
    ch[y][dir] = w, fa[w] = y;
    ch[p][dir ^ 1] = y, fa[y] = p;
    pushup(y), pushup(p), pushup(z);
}

inline void jump(int p)
{
    if (!isRoot(p))
        jump(fa[p]);
    pushdown(p);
}

inline void splay(int p)
{
    jump(p);
    for (int fat = fa[p]; fat = fa[p], !isRoot(p); rotate(p))
        if (!isRoot(fat))
            rotate(check(fat) == check(p) ? fat : p);
}

inline void access(int p)
{
    for (int fat = 0; p != 0; fat = p, p = fa[p])
        splay(p), ch[p][1] = fat, pushup(p);
}

inline void makeRoot(int p)
{
    access(p), splay(p);
    swap(lson, rson), tag[p] ^= 1;
}

inline int find(int p)
{
    access(p), splay(p);
    while (lson)
        p = lson;
    splay(p);
    return p;
}

inline void link(int x, int y)
{
    makeRoot(x);
    fa[x] = y;
}

inline void split(int x, int y)
{
    makeRoot(x);
    access(y), splay(y);
}

inline bool check(int x, int y)
{
    makeRoot(x);
    return find(y) == x;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d%d", &edges[i].src, &edges[i].dst, &edges[i].ai, &edges[i].bi);

    int ans = 2e9;
    sort(edges + 1, edges + 1 + m);

    for (int i = 1; i <= m; i++)
    {
        int id = i + n;
        val[id] = edges[i].bi;
        if (edges[i].src == edges[i].dst)
            continue;
        if (!check(edges[i].src, edges[i].dst))
            link(edges[i].src, id), link(id, edges[i].dst);
        else
        {
            split(edges[i].src, edges[i].dst);
            int now = idx[edges[i].dst], maxb = val[now];
            if (maxb <= edges[i].bi)
                continue;
            splay(now), fa[ch[now][0]] = fa[ch[now][1]] = 0;
            link(edges[i].src, id), link(id, edges[i].dst);
        }
        if (check(1, n))
            split(1, n), ans = min(ans, edges[i].ai + val[idx[n]]);
    }
    if (ans < 2e9)
        printf("%d", ans);
    else
        puts("-1");
    return 0;
} // P2387.cpp

Leave a Reply

Your email address will not be published. Required fields are marked *