蒟蒻求助
查看原帖
蒟蒻求助
32527
SD191553楼主2018/10/6 22:53

本蒟蒻写了个树剖的板子然而WA完了,而且自己输出的和数据毫无规律的不同,求各位大佬支援一下。

#include<bits/stdc++.h>
using namespace std;
#define lc (p<<1)
#define rc (p<<1|1)
#define N 100010
typedef long long ll;
ll read(){
    ll sum=0,neg=1;
    char c=getchar();
    while((c>'9'||c<'0')&&c!='-') c=getchar();
    if(c=='-') neg=-1,c=getchar();
    while(c>='0'&&c<='9') sum=(sum<<3)+(sum<<1)+c-'0',c=getchar();
    return sum*neg;
}
struct Edge{
    int u,v;
}e[N<<1];
int first[N],nxt[N<<1],cnt=0;
int depth[N],size[N],son[N],top[N],fa[N],wu[N];
int ide[N],dfs_clock=0;
long long val[N];
void AddEdge(int u,int v){
    e[++cnt].u=u;e[cnt].v=v;
    nxt[cnt]=first[u];first[u]=cnt;
}
struct Node{
    int l,r,lazy;
    ll sum;
};
struct SegmentTree{
    Node T[N<<2];
    inline void pushnow(int p,int v){
        T[p].sum+=(T[p].r-T[p].l+1)*v;
        T[p].lazy+=v;
    }
    inline void pushup(ll p){
        T[p].sum=T[lc].sum+T[rc].sum;
    }
    inline void pushdown(ll p){
        if(!T[p].lazy){
            pushnow(lc,T[p].lazy);
            pushnow(rc,T[p].lazy);
            T[p].lazy=0;
        }
    }
    void build(int p,int l,int r){
        T[p].l=l,T[p].r=r;
        if(l==r){
            T[p].sum=val[wu[l]]; T[p].lazy=0;
            return;
        }
        ll mid=(l+r)>>1;
        build(lc,l,mid);
        build(rc,mid+1,r);
        pushup(p);
    }
    void update(ll p,ll ql,ll qr,ll v){
        if(ql<=T[p].l&&qr>=T[p].r){
            pushnow(p,v);
            return;
        }
        ll mid=(T[p].l+T[p].r)>>1;
        pushdown(p);
        if(ql<=mid) update(lc,ql,qr,v);
        if(qr>mid) update(rc,ql,qr,v);
        pushup(p);
    }
    ll query(int p,int ql,int qr){
        if(ql<=T[p].l&&qr>=T[p].r) return T[p].sum;
        ll mid=(T[p].l+T[p].r)>>1;
        pushdown(p);
        ll ans=0;
        if(ql<=mid) ans+=query(lc,ql,qr);
        if(qr>mid) ans+=query(rc,ql,qr);
        pushup(p);
        return ans;
    }
}Tree;
void dfs1(int u){
    size[u]=1;
    depth[u]=depth[fa[u]]+1;
    for(int i=first[u];i;i=nxt[i]){
        int v=e[i].v;
        if(v==fa[u]) continue;
        fa[v]=u;
        dfs1(v);
        size[u]+=size[v];
        if(size[son[u]]<size[v]) son[u]=v;
    }
}
void dfs2(int u,int topf){
    ++dfs_clock;
    top[u]=topf;
    ide[u]=dfs_clock;
    wu[ide[u]]=u;
    if(!son[u]) return;
    dfs2(son[u],topf);
    for(int i=first[u];i;i=nxt[i]){
        int v=e[i].v;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
void modify_path(int u,int v,int d){
    while(top[u]!=top[v]){
        if(depth[top[u]]<depth[top[v]]) swap(u,v);
        Tree.update(1,ide[top[u]],ide[u],d);
        u=fa[top[u]];
    }
    if(depth[u]>depth[v]) swap(u,v);
    Tree.update(1,ide[u],ide[v],d);
}
ll n;
int main(){
    n=read();
    for(int i=1;i<n;i++){
        int a,b;
        a=read(); b=read();
        a++; b++;
        //cout<<a<<" "<<b<<endl;
        AddEdge(a,b);
        AddEdge(b,a);
    }
    dfs1(1);
    dfs2(1,1);
    Tree.build(1,1,n);
    /*for(int i=1;i<=n;i++) cout<<ide[i]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++) cout<<fa[i]<<" ";*/
    int q;
    q=read();
    for(int i=1;i<=q;i++){
        char cmd;
        scanf("%s",&cmd);
        if(cmd=='A'){
            int u,v,d;
            u=read(); v=read(); d=read();
            u++; v++;
            modify_path(u,v,d);
        }
        else if(cmd=='Q'){
            int u;
            u=read();
            u++;
            ll ans=Tree.query(1,ide[u],ide[u]+size[u]-1);
            printf("%lld\n",ans);
        }
    }
}
2018/10/6 22:53
加载中...