[洛谷P1501][国家集训队]Tree II

题目大意：给一棵树，有四种操作：

1. $+\;u\;v\;c：$将路径$u->v$区间加$c$
2. $-\;u_1\;v_1\;u_2\;v_2：$将边$u_1-v_1$切断，改成边$u_2-v_2$，保证数据合法
3. $*\;u\;v\;c：$将路径$u->v$区间乘$c$
4. $/\;u\;v：$询问路径$u->v$区间和

题解：$LCT$乱搞

卡点：无

C++ Code：

#include <cstdio>
#define maxn 100010
#define lc(rt) son[rt][0]
#define rc(rt) son[rt][1]
const long long mod = 51061;
int n, q;
long long V[maxn], s[maxn], tg[maxn], M[maxn], A[maxn];
int son[maxn][2], fa[maxn], sz[maxn];
inline void swap(int &a, int &b) {a ^= b ^= a ^= b;}
inline void swap(int x) {
    swap(lc(x), rc(x));
    tg[lc(x)] ^= 1, tg[rc(x)] ^= 1, tg[x] = 0;
}
inline void setmul(int x) {
    long long &tmp = M[x];
    M[lc(x)] = M[lc(x)] * tmp % mod, M[rc(x)] = M[rc(x)] * tmp % mod;
    A[lc(x)] = A[lc(x)] * tmp % mod, A[rc(x)] = A[rc(x)] * tmp % mod;
    V[lc(x)] = V[lc(x)] * tmp % mod, V[rc(x)] = V[rc(x)] * tmp % mod;
    s[lc(x)] = s[lc(x)] * tmp % mod, s[rc(x)] = s[rc(x)] * tmp % mod;
    tmp = 1;
}
inline void setadd(int x) {
    long long &tmp = A[x];
    A[lc(x)] = (A[lc(x)] + tmp) % mod, A[rc(x)] = (A[rc(x)] + tmp) % mod;
    V[lc(x)] = (V[lc(x)] + tmp) % mod, V[rc(x)] = (V[rc(x)] + tmp) % mod;
    s[lc(x)] = (s[lc(x)] + sz[lc(x)] * tmp) % mod, s[rc(x)] = (s[rc(x)] + sz[rc(x)] * tmp) % mod;
    tmp = 0;
}
inline void pushdown(int x) {
    if (tg[x]) swap(x);
    if (M[x] != 1) setmul(x);
    if (A[x]) setadd(x);
}
inline void update(int x) {
    s[x] = (s[lc(x)] + s[rc(x)] + V[x]) % mod;
    sz[x] = sz[lc(x)] + sz[rc(x)] + 1;
}
inline int get(int x) {return rc(fa[x]) == x;}
inline bool isrt(int x) {return lc(fa[x]) != x && rc(fa[x]) != x;}
inline void rotate(int x) {
    int y = fa[x], z = fa[y], b = get(x);
    if (!isrt(y)) son[z][get(y)] = x;
    fa[son[y][b] = son[x][!b]] = y; son[x][!b] = y;
    fa[y] = x, fa[x] = z;
    update(y), update(x);
}
int S[maxn], top;
inline void splay(int x) {
    S[top = 1] = x;
    for (int y = x; !isrt(y); S[++top] = y = fa[y]);
    for (; top; top--) pushdown(S[top]);
    for (; !isrt(x); rotate(x)) if (!isrt(fa[x])) 
        get(x) ^ get(fa[x]) ? rotate(x) : rotate(fa[x]);
    update(x);
}
inline void access(int x) {for (int t = 0; x; rc(x) = t, t = x, x = fa[x]) splay(x);}
inline void mkrt(int x) {access(x), splay(x), tg[x] ^= 1;}
inline void link(int x, int y) {mkrt(x), fa[x] = y;}
inline void split(int x, int y) {mkrt(x), access(y), splay(y);}
inline void cut(int x, int y) {split(x, y), lc(y) = fa[x] = 0;}
inline void add(int x, int y, long long num) {
    split(x, y);
    A[y] = (A[y] + num) % mod;
    V[y] = (V[y] + num) % mod;
    s[y] = (s[y] + sz[y] * num) % mod;
}
inline void mul(int x, int y, long long num) {
    split(x, y);
    A[y] = A[y] * num % mod;
    V[y] = V[y] * num % mod;
    M[y] = M[y] * num % mod;
    s[y] = s[y] * num % mod;
}
inline long long query(int x, int y) {
    split(x, y);
    pushdown(y);
    return s[y];
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) V[i] = 1, M[i] = 1, s[i] = 1;
    for (int i = 1; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        link(a, b);
    }
    while (q --> 0) {
        int x, y;
        long long z;
        char op[10];
        scanf("%s%d%d", op, &x, &y);
        switch (*op) {
            case '+': scanf("%lld", &z), add(x, y, z); break;
            case '-': cut(x, y), scanf("%d%d", &x, &y), link(x, y); break;
            case '*': scanf("%lld", &z), mul(x, y, z); break;
            case '/': printf("%lld\n", query(x, y));
        }
    }
    return 0;
}
           

转载于:https://www.cnblogs.com/Memory-of-winter/p/9657097.html