【题解】BZOJ 2759 一个动态树好题

请注意,本文编写于 93 天前,最后修改于 93 天前,其中某些信息可能已经过时。

Problem

有 $n$ 个未知数,每个未知数都有一个方程描述:

$$ x[i]=k[i]*x[p[i]]+b[i] \bmod 10007 $$

有 $m$ 个操作,每个操作可能是下面两种情况之一:

  1. 询问当前 $x[a]$ 的解
  2. 修改一个等式

Thought

我不是一个动态树题

如果将 $x[i]$ 和 $x[p[i]]$ 连接起来,最后形成的图显然是一个基环树森林

考虑将 $k[i],b[i]$ 信息放到边中

对于基环树的环上部分,显然是可以直接算出解的
对于基环树的树上部分,可以通过和环上的连接算出解

如何维护边的信息呢?

考虑使用 LCT ,选择基环树上的一条边删去,维护剩下的树的信息

假设被删去的边为 $(x,y)$ ,显然就可以通过两条路径也就是两个方程将 $y$ 的取值解出来

使 $x$ 为根,那么所有点到 $x$ 的路径都是由 $i\Rightarrow p[i]$ 连成的,那么任意一个点就很方便的能用 $y$ 表示出来(为什么是 $y$ ?其实 $x$ 也可以,但是 $y$ 更加自然,为什么呢?)

一个比较方便的修改方法是:删除原边,尝试加入基环树上的边,尝试加入新边,这样就不需要分类讨论,在形成环的同时维护答案即可

记得在 Splay 上维护 $kx+b$ 时要注意顺序

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 30010;
const int mod = 10007;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int qpow(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
#define L (ch[x][0])
#define R (ch[x][1])
struct LCT {
    int ch[N][2], fa[N], k[N], b[N], p[N], rev[N], sta[N], top;
    int var[N], con[N], Ans[N];
    void upd(int x) {
        var[x] = var[L] * k[x] % mod;
        con[x] = con[L] * k[x] % mod;
        con[x] = (con[x] + b[x]) % mod;

        var[x] = var[x] * var[R] % mod;
        con[x] = con[x] * var[R] % mod;
        con[x] = (con[x] + con[R]) % mod;
    }
    bool get(int x) {
        return ch[fa[x]][1] == x;
    }
    bool isr(int x) {
        return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
    }
    void rotate(int x) {
        int old = fa[x], oldf = fa[old], w = get(x);
        if(!isr(old))
            ch[oldf][ch[oldf][1] == old] = x;
        ch[old][w] = ch[x][w ^ 1]; fa[ch[old][w]] = old;
        ch[x][w ^ 1] = old; fa[old] = x;
        fa[x] = oldf;
        upd(old); upd(x);
    }
    void splay(int x) {
        for(int f; !isr(x); rotate(x))
            if(!isr(f = fa[x]))
                rotate(get(x) == get(f) ? f : x);
    }
    void access(int x) {
        for(int i = 0; x; i = x, x = fa[x]) {
            splay(x);
            R = i;
            upd(x);
        }
    }
    int find(int x) {
        access(x);
        splay(x);
        while(ch[x][0]) x = ch[x][0];
        return x;
    }
    bool link(int x, int y) { 
        int fx = find(x), fy = find(y);
        if(fx == fy)
            return 0;
        access(x);
        splay(x);
        fa[x] = y;
        return 1;
    }
    void cut(int x, int y) {
        access(x);
        splay(y);
        ch[y][1] = 0;
        fa[x] = 0;
        upd(y);
    }
    void connect(int x) {
        if(link(x, p[x])) return;
        access(p[x]);
        splay(p[x]);
        int K = (1 - var[p[x]] + mod) % mod;
        int B = con[p[x]];
        if(K == 0)
            if(B == 0)
                Ans[p[x]] = - 2;
            else
                Ans[p[x]] = - 1;
        else
            Ans[p[x]] = con[p[x]] * qpow(K, mod - 2) % mod;
    }
    void query(int x) {
        int sr = p[find(x)];
        //access & splay successful
        int K = var[x];
        int B = con[x];
        
        if(Ans[sr] == - 1)
            printf("%d\n", Ans[sr]);
        else
            if(K == 0) printf("%d\n", B);
            else if(Ans[sr] < 0) printf("%d\n", Ans[sr]);
            else printf("%d\n", (Ans[sr] * K % mod + B) % mod);
    }
    void change(int X, int K, int P, int B) {
        int x = find(X);
        //access & splay successful
        if(X == x) {
            k[X] = K; p[X] = P; b[X] = B;
            upd(X);
            connect(X);
        }
        else {
            cut(X, p[X]);
            connect(x);
            k[X] = K; p[X] = P; b[X] = B;
            upd(X);
            connect(X);
        }
    }
}tr;
int n, m;
char s[2];
int main() {
    #ifdef DIFF
        freopen("in", "r", stdin);
        freopen("main.out", "w", stdout);
    #endif
    #ifndef DIFF
        #ifndef ONLINE_JUDGE
            freopen("in", "r", stdin);
        #endif
    #endif
    n = read();
    tr.var[0] = tr.k[0] = 1;
    for(int i = 1; i <= n; ++ i) {
        tr.k[i] = read();
        tr.p[i] = read();
        tr.b[i] = read();
        tr.upd(i);
        tr.connect(i);
    }
    m = read();
    for(int i = 1; i <= m; ++ i) {
        scanf("%s", s);
        if(s[0] == 'A') {
            int x = read();
            tr.query(x);
        }
        else {
            int X = read(), K = read(), P = read(), B = read();
            tr.change(X, K, P, B);
        }
    }
    return 0;
}
Comments

添加新评论