题解：P3637 方程组

Aron_2023 · 2024-12-08 22:48:56 · 题解

前置知识

前置知识：LCT

LCT（Link-Cut Tree）是一种高效的数据结构，用于解决动态树问题，即在树形结构上进行动态的连接（Link）和切割（Cut）操作。LCT 是由 Robert Tarjan 在 1989 年提出的，它结合了二叉搜索树（BST）和树的动态连接操作的特点，使得在树上进行路径相关查询和更新操作的时间复杂度可以达到近线性时间。

接着，我们来学习 LCT 该如何实现以及它的效果，比如下面这道题：

维护一棵树，支持如下操作：

修改两点间路径权值。

查询两点间路径权值和。

修改某点子树权值。

查询某点子树权值和。

断开并连接一些边，保证仍是一棵树。

这道题就可以使用 LCT 求解。

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int INF = 1e9;

struct Node {
    int parent, size;
    long long weight;
    Node *left, *right;
    Node() : parent(-1), size(1), weight(0), left(nullptr), right(nullptr) {}
};

Node* T[MAXN];
int cnt;

void init() {
    for (int i = 0; i < MAXN; ++i) T[i] = nullptr;
    cnt = 0;
}

Node* new_node(int p = -1, long long w = 0) {
    T[cnt] = new Node();
    T[cnt]->parent = p;
    T[cnt]->weight = w;
    return T[cnt++];
}

void splay(Node* x) {
    while (x->parent != -1) {
        Node* y = T[x->parent];
        if (y->parent == -1) {
            if (y->right == x) swap(x, y->right);
            else swap(x, y->left);
        } else {
            Node* z = T[y->parent];
            if (z->left == y) {
                if (y->left == x) {
                    swap(x, y->left);
                    swap(y, x->right);
                } else if (y->right == x) {
                    swap(x, y->right);
                    swap(y, x->left);
                }
            } else {
                if (y->left == x) {
                    swap(x, y->left);
                    swap(y, x->right);
                } else if (y->right == x) {
                    swap(x, y->right);
                    swap(y, x->left);
                }
            }
        }
    }
}

void access(Node* x) {
    while (x != nullptr) {
        splay(x);
        x->left = nullptr;
        x->right = (x->parent != -1) ? T[x->parent] : nullptr;
        x = T[x->parent];
    }
}

void makeroot(Node* x) {
    access(x);
    splay(x);
    swap(x, x->right);
}

void link(Node* x, Node* y) {
    makeroot(x);
    access(y);
    splay(y);
    x->parent = y->parent = -1;
    x->right = y;
}

void cut(Node* x, Node* y) {
    makeroot(y);
    access(x);
    splay(x);
    x->parent = -1;
}

int main() {
    init();
    Node* root = new_node();
    // 假设我们有节点 1 和 2，并且想要将它们连接起来
    Node* node1 = new_node(root, 10);
    Node* node2 = new_node(root, 20);
    link(node1, node2);
    // 进行其他操作...
    return 0;
}

上面的代码展示的是 LCT 的基本操作的一部分，读者可以自己去网络上搜索有关于 LCT 算法的其他内容。

分析

本题就是对边操作的 LCT，把边化成点，然后操作。

这道题目从 a 到 b 和从 b 到 a 是不一样的，所以在反转的时候要将权值乘 -1 。

AC Code

只放核心代码：

struct node
{
    int rev,w,sum;
    node *f,*ch[2];
}nd[maxn],*s[maxn];
int getwh(node *x)
{if(!x->f) return -1;if(x->f->ch[0]==x)return 0;if(x->f->ch[1]==x)return 1;return -1;}
bool isroot(node *x){return getwh(x)==-1;}
void join(node *x, node *y, int wh){if(x)x->f=y;if(y)y->ch[wh]=x;}
void rev(node *x){if(x)x->rev^=1;}
void pushdown(node *x)
{
    if(!x)return;
    if(x->rev)
    {
        x->w=-x->w;x->sum=-x->sum;swap(x->ch[0],x->ch[1]);
        rev(x->ch[0]),rev(x->ch[1]);
        x->rev=0;
    }
}
void pushup(node *x)
{
    pushdown(x->ch[0]);
    pushdown(x->ch[1]);
    x->sum=x->w;
    if(x->ch[0])x->sum+=x->ch[0]->sum;
    if(x->ch[1])x->sum+=x->ch[1]->sum;
}
void rotate(node *x)
{
    node *y=x->f,*z=y->f;
    int c=getwh(x);
    if(isroot(y))x->f=y->f;
    else join(x,z,getwh(y));
    join(x->ch[!c],y,c),join(y,x,!c);
    pushup(y);
    pushup(x);
}
void splay(node *x)
{
    node *y; int top=0;
    for(y=x;!isroot(y);y=y->f)s[++top]=y;s[++top]=y;
    for(;top;top--)pushdown(s[top]);
    while(!isroot(x))
    {
        y=x->f;
        if(isroot(y)){rotate(x);return;}
        if(getwh(x)^getwh(y))rotate(x);else rotate(y);
        rotate(x);
    }
}
void access(node *x)
{
    node *t=0;
    while(x)
    {
        splay(x);
        x->ch[1]=t;
        pushup(x);
        t=x,x=x->f;
    }
}
void makeroot(node *x) {access(x);splay(x);rev(x);}
void link(node *x,node *y) {makeroot(x);x->f=y;}
void cut(node *x,node *y)
{
    makeroot(x);access(y);splay(y);
    if(y->ch[0]==x and !x->ch[1])x->f=y->ch[0]=0;
}
node* findroot(node *x)
{
    while(x->f)x=x->f;
    return x;
}