书剖+线段树WA了7个点,有偿找错误
查看原帖
书剖+线段树WA了7个点,有偿找错误
1143200
Dylan_1楼主2024/5/8 00:10

请各位大佬帮忙看看,非常感谢; 15RMB报酬

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+50;
vector<int>tree[maxn];
int fa[maxn],depth[maxn],son[maxn],sz[maxn];
int top[maxn],id[maxn],cnt;
int n,Q;
void dfs1(int u,int f){
    depth[u]=depth[f]+1;
    fa[u]=f;
    sz[u]=1;
    for(int v:tree[u]){
        if(v==f) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[son[u]]<sz[v]){
            son[u]=v;
        }
    }
}

void dfs2(int u,int t){
    top[u]=t;
    id[u]=++cnt;
    if(!son[u]) return;
    dfs2(son[u],t);
    for(int v:tree[u]){
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}

struct Segtree{
    int l,r;
    int add,val;
}t[maxn*4];

void push_up(int p){
    t[p].val=t[p*2].val+t[p*2+1].val;
}

void push_down(int p){
    if(t[p].add){
        t[p*2].add+=t[p].add;
        t[p*2+1].add+=t[p].add;
        t[p*2].val+=t[p].add*(t[p*2].r-t[p*2].l+1);
        t[p*2+1].val+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
        t[p].add=0;
    }
}

void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    t[p].add=0,t[p].val=0;
    if(l==r) return;
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    push_up(p);
}

void change(int p,int l,int r,int d){
    if(l<=t[p].l&&t[p].r<=r){
        t[p].add+=d;
        t[p].val+=d*(t[p].r-t[p].l+1);
        return;
    }
    push_down(p);
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid) change(p*2,l,r,d);
    if(mid<r) change(p*2+1,l,r,d);
    push_up(p);
}

long long ask(int p,int l,int r){
    if(l<=t[p].l&&t[p].r<=r){
        return t[p].val;
    }
    push_down(p);
    int mid=(t[p].l+t[p].r)/2;
    long long ans=0L;
    if(l<=mid) ans+=ask(p*2,l,r);
    if(mid<r) ans+=ask(p*2+1,l,r);
    return ans;
}

long long ask_tree(int u){
    return ask(1,id[u],id[u]+sz[u]-1);
}

void change_path(int u,int v,int d){
    while(top[u]!=top[v]){
        if(depth[u]<depth[v]) swap(u,v);
        change(1,id[top[u]],id[u],d);
        u=fa[top[u]];
    }
    if(depth[u]<depth[v]) swap(u,v);
    change(1,id[v],id[u],d);
}

int main(){
    cin>>n;
    for(int i=0;i<n-1;++i){
        int a,b;
        cin>>a>>b;
        ++a,++b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    cin>>Q;
    /*
    cout<<"\n"<<endl;
    cout<<"q="<<q<<endl;
    */
    for(int i=0;i<Q;++i){
        char opt;
        cin>>opt;
        if(opt=='A'){
            int u,v,d;
            cin>>u>>v>>d;
            ++u,++v;
            /*
            cout<<endl;
            cout<<"u,v,d="<<u<<v<<d<<endl;
            */
            change_path(u,v,d);
        }
        if(opt=='Q'){
            int u;
            cin>>u;
            ++u;
            /*
            cout<<"\n";
            cout<<"u="<<u<<endl;
            */
            long long ans=ask_tree(u);
            cout<<ans<<endl;
        }
    }
    return 0;
}
2024/5/8 00:10
加载中...