萌新,刚学,不会,求助

回复帖子

@function_of_zero 2019-10-06 13:26 回复

本地RE提交WA。

已知dfs1就会RE,而题解代码也会RE,所以目测是由于我的电脑太渣使得被#2恶意卡成栈溢出。所以我就没法调了……

已知答案会偏大。

#include<algorithm>
#include<vector>
#include<cctype>
#include<cstdio>
using namespace std;
inline int readint(){
    int x=0;
    bool f=0;
    char c=getchar();
    while(!isdigit(c)&&c!='-') c=getchar();
    if(c=='-'){
        f=1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return f?-x:x;
}
const int maxn=1e5+5;
int n,m,r,p,w[maxn];
vector<int> g[maxn];
int deep[maxn],size[maxn],hson[maxn],fa[maxn];
void dfs1(int u){
    deep[u]=deep[fa[u]]+1;
    size[u]=1;
    hson[u]=0;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(v==fa[u]) continue;
        fa[v]=u;
        dfs1(v);
        size[u]+=size[v];
        if(size[v]>size[hson[u]]) hson[u]=v;
    }
}
vector<int> f;
int top[maxn],pos[maxn];
void dfs2(int u){
    pos[u]=f.size();
    f.push_back(w[u]);
    if(hson[u]){
        top[hson[u]]=top[u];
        dfs2(hson[u]);
    }
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(v==fa[u]||v==hson[u]) continue;
        top[v]=v;
        dfs2(v);
    }
}
struct node{
    int l,r;
    int sumv,addv;
    node* ch[2];
    void maintain(){
        sumv=0;
        sumv=((sumv+ch[0]->sumv)%p+ch[0]->addv*(ch[0]->r-ch[0]->l+1)%p)%p;
        sumv=((sumv+ch[1]->sumv)%p+ch[1]->addv*(ch[1]->r-ch[1]->l+1)%p)%p;
    }
    node(int l,int r):l(l),r(r),addv(0){
        if(l<r){
            int mid=l+(r-l)/2;
            ch[0]=new node(l,mid);
            ch[1]=new node(mid+1,r);
            maintain();
        }
        else{
            sumv=f[r];
            ch[0]=ch[1]=0;
        }
    }
    void pushdown(){
        if(l<r){
            ch[0]->addv=(ch[0]->addv+addv)%p;
            ch[1]->addv=(ch[1]->addv+addv)%p;
        }
        sumv=(sumv+addv*(r-l+1)%p)%p;
        addv=0;
    }
    void update(int l,int r,int k){
        pushdown();
        if(l==this->l&&r==this->r) addv=k;
        else if(r<=ch[0]->r) ch[0]->update(l,r,k);
        else if(l>=ch[1]->l) ch[1]->update(l,r,k);
        else{
            ch[0]->update(l,ch[0]->r,k);
            ch[1]->update(ch[1]->l,r,k);
        }
        if(this->l<this->r) maintain();
    }
    int query(int l,int r){
        pushdown();
        if(l==this->l&&r==this->r) return sumv;
        else if(r<=ch[0]->r) return ch[0]->query(l,r);
        else if(l>=ch[1]->l) return ch[1]->query(l,r);
        else return (ch[0]->query(l,ch[0]->r)+ch[1]->query(ch[1]->l,r))%p;
    }
}*rt;
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    n=readint();
    m=readint();
    r=readint();
    p=readint();
    for(int i=1;i<=n;i++) w[i]=readint()%p;
    for(int i=1;i<n;i++){
        int x,y;
        x=readint();
        y=readint();
        g[x].push_back(y);
        g[y].push_back(x);
    }
    deep[0]=0;
    size[0]=0;
    fa[r]=0;
    dfs1(r);
    top[r]=r;
    dfs2(r);
    rt=new node(0,n-1);
    while(m--){
        int opt=readint();
        if(opt==1){
            int x,y,z;
            x=readint();
            y=readint();
            z=readint()%p;
            while(top[x]!=top[y]){
                if(deep[x]<deep[y]) swap(x,y);
                rt->update(pos[top[x]],pos[x],z);
                x=fa[top[x]];
            }
            if(deep[x]<deep[y]) swap(x,y);
            rt->update(pos[y],pos[x],z);
        }
        else if(opt==2){
            int x,y;
            x=readint();
            y=readint();
            int ans=0;
            while(top[x]!=top[y]){
                if(deep[x]<deep[y]) swap(x,y);
                ans=(ans+rt->query(pos[top[x]],pos[x]))%p;
                x=fa[top[x]];
            }
            if(deep[x]<deep[y]) swap(x,y);
            ans=(ans+rt->query(pos[y],pos[x]))%p;
            printf("%d\n",ans);
        }
        else if(opt==3){
            int x,z;
            x=readint();
            z=readint()%p;
            rt->update(pos[x],pos[x]+size[x]-1,z);
        }
        else{
            int x=readint();
            printf("%d\n",rt->query(pos[x],pos[x]+size[x]-1));
        }
    }
    return 0;
}
@Alpha 2019-10-06 13:57 回复 举报

$\color{white}\huge\text{QNDMX}$

$\color{white}\huge\text{QNDGXOI}$

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



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