萌新求助,样例,AC,提交WA。。。

回复帖子

@zhoukangyang 2020-07-15 18:53 回复
#include<bits/stdc++.h>
#define N 114514
#define mod 51061
#define ls ch[x][0]
#define rs ch[x][1]
#define uint unsigned int
using namespace std;
int ch[N][2],fa[N],flag[N];
uint lazya[N],lazyb[N],ans[N],val[N];
int get(int x) {
    return (ch[fa[x]][0] == x || ch[fa[x]][1] == x);
}
void flip(int x) {
    if(x) swap(ch[x][0],ch[x][1]),flag[x]^=1;
}
void addlazy(int id,uint x,uint y) {
    if(!id) return;
    ans[id] = (ans[id] * x + y) % mod;
    lazya[id] = lazya[id] * x % mod;
    lazyb[id] = (lazyb[id] * x + y) % mod;
    val[id] = (val[id] * x + y) % mod;
}
void pushdown(int x) {
    addlazy(ls,lazya[x],lazyb[x]),addlazy(rs,lazya[x],lazyb[x]);
    lazya[x] = 1, lazyb[x] = 0;
    if(flag[x]) flip(ls),flip(rs),flag[x] = 0;
}
void upd(int x) {
    pushdown(x),ans[x] = (ans[ls] + ans[rs] + val[x]) % mod;
}
void rotate(int x) {
    int y = fa[x], z = fa[y], fson = (ch[y][1] == x), ano = ch[x][1^fson];
    if(get(y)) ch[z][ch[z][1]==y] = x;
    if(ano) fa[ano] = y;
    fa[y] = x, ch[x][1^fson] = y, fa[x] = z, ch[y][fson] = ano;
    upd(y),upd(x);
}
int fx,tot,f[N];
void Splay(int x) {
    tot = 1, f[tot] = fx = x;
    while(get(fx)) ++tot, f[tot] = fx = fa[fx];
    while(tot) pushdown(f[tot]), tot--;
    while(get(x)) {
        int y = fa[x], z = fa[y];
        if(get(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
        rotate(x);
    }
    upd(x);
}
void access(int x) {
    int y = 0;
    while(x) {
        Splay(x);
        ch[x][1] = y;
        upd(x);
        y = x;
        x = fa[x];
    }
}
void makeroot(int x) {
    access(x),Splay(x),flip(x);
}
int findroot(int x) {
    access(x),Splay(x), pushdown(x);
    while(ch[x][0]) x = ch[x][0], pushdown(x);
    Splay(x);
    return x;
}
void split(int x,int y) {
    makeroot(x),access(y),Splay(y);
}
void link(int x,int y) {
    makeroot(x);
    if(findroot(y) != x) findroot(y), fa[x] = y;
}
void cut(int x,int y) {
    makeroot(x);
    if(findroot(y) == x && fa[y] == x && !ch[y][0]) fa[y] = ch[x][1] = 0, upd(x);
}
int n,m,s,x,y,z;
char opt[1000];
signed main() {
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) ans[i] = val[i] = lazya[i] = 1;
    for(int i = 1; i < n; i++) {
        scanf("%d%d",&x,&y);
        link(x,y);
    }
    while(m--) {
        scanf("%s%d%d",opt,&x,&y);
        if(opt[0] == '+') scanf("%d",&z),split(x,y),addlazy(y,1,z);
        if(opt[0] == '-') scanf("%d%d",&s,&z),cut(x,y),link(s,z);
        if(opt[0] == '*') scanf("%d",&z),split(x,y),addlazy(y,z,0);
        if(opt[0] == '/') split(x,y),printf("%d\n",ans[y]);
    }
    return 0;
}

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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