萌新求助,本地能过,你谷MLE。

回复帖子

@too_late 2020-10-16 19:31 回复

以下:(

#include <bits/stdc++.h>
#define I inline
#define int long long
#define RI register int
#define ls ch[p][0]
#define rs ch[p][1]
#define N 100005
#define mo 51061
using namespace std;

class LCT{
public:
    int top, st[N], f[N], ch[N][2], val[N], add[N], mul[N], sum[N], sz[N], tag[N];
    I int up(int p){ sz[p] = sz[ls] + sz[rs] + 1, sum[p] = (sum[ls] + sum[rs] + val[p]) % mo; }
    I void down(int p){
        if(tag[p]){ ls ^= rs ^= ls ^= rs, tag[ls] ^= 1, tag[rs] ^= 1, tag[p] = 0; }
        long long mu = mul[p], ad = add[p];
        if(mu != 1){
            mul[ls] = (mul[ls] * mu) % mo; mul[rs] = (mul[rs] * mu) % mo;
            add[ls] = (add[ls] * mu) % mo; add[rs] = (add[rs] * mu) % mo;
            sum[ls] = (sum[ls] * mu) % mo; sum[rs] = (sum[rs] * mu) % mo;
            val[ls] = (val[ls] * mu) % mo; val[rs] = (val[rs] * mu) % mo; mul[p] = 1;
        } if(ad){
            add[ls] = (add[ls] + ad) % mo; add[rs] = (add[rs] + ad) % mo;
            sum[ls] = (sum[ls] + ad * sz[ls]) % mo; sum[rs] = (sum[rs] + ad * sz[rs]) % mo;
            val[ls] = (val[ls] + ad) % mo; val[rs] = (val[rs] + ad) % mo; add[p] = 0;
        }
    }
    I bool isroot(int p){ return p != ch[f[p]][0] && p != ch[f[p]][1]; }
    I int get(int p){ return p == ch[f[p]][1]; }
    I void rotate(int x){
        int y = f[x], z = f[y], k = get(x); if(!isroot(y)) ch[z][ch[z][1] == y] = x;
        ch[y][k] = ch[x][!k], f[ch[x][!k]] = y, ch[x][!k] = y, f[y] = x, f[x] = z, up(y), up(x);
    }
    I void splay(int x){
        RI i,fa; st[top = 1] = i = x; while(!isroot(i)) st[++top] = i = f[i];
        while(top) down(st[top--]); for(; fa = f[x], !isroot(x); rotate(x))
            if(!isroot(fa)) rotate(get(fa) == get(x)? fa: x);
    }void print(int p) { if (!p) return; down(p); print(ls); printf("%lld ", p); print(rs); }

    I void access(int p){ RI q; for(q = 0; p; q = p, p = f[p]) splay(p), rs = q, up(p); }
    I void makeroot(int p){ access(p), splay(p), tag[p] ^= 1; }
    I int findroot(int p){ splay(p); while(ls) p = ls; return splay(p), p; }
    I void split(int x, int y){ makeroot(x); access(y), splay(y); }
    I void link(int x, int y){ makeroot(x); if(findroot(y) != x) f[x] = y; }
    I void cut(int x, int y){ split(x, y); if(ch[y][0] == x) ch[y][0] = f[x] = 0; up(x); }
} tr;

int n, m, x, y, z, c;
char op[10];

signed main(){
    RI i; for(i = 1; i < N; i++) tr.mul[i] = tr.val[i] = tr.sz[i] = 1; tr.val[0] = 0;
    for(scanf("%d%d", &n, &m), i = 1; i < n; i++) scanf("%d%d", &x, &y), tr.link(x, y);
    for(i = 1; i <= m; i++){ scanf("%s", op + 1);
        for(int i = 1; i <= n; i++) tr.down(i);
        if(op[1] == '+') scanf("%d%d%d", &x, &y, &z), tr.split(x, y), tr.val[y] = (tr.val[y] + z) % mo,
            tr.sum[y] = (tr.sum[y] + z * tr.sz[y]) % mo, tr.add[y] = (tr.add[y] + z) % mo;
        if(op[1] == '*') scanf("%d%d%d", &x, &y, &z), tr.split(x, y), tr.val[y] = (tr.val[y] * z) % mo,
            tr.sum[y] = (tr.sum[y] * z) % mo, tr.mul[y] = (tr.mul[y] * z) % mo;
        if(op[1] == '-') scanf("%d%d%d%d", &x, &y, &z, &c), tr.cut(x, y), tr.link(z, c);
        if(op[1] == '/') scanf("%d%d", &x, &y), tr.split(x, y), printf("%d\n", tr.sum[y]);
    }
    exit(0);
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。