样例不过求条 悬3关
查看原帖
样例不过求条 悬3关
322792
Alea楼主2024/1/7 22:44
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,iwg[N],sum[N*4],tag[N*4],wg[N];
vector<int> tr[N];
int wson[N],dfn[N],siz[N],nfd[N],dft;
void subd(int u){
    siz[u]=1;
    for(int v:tr[u]){
        subd(v);
        siz[u]+=siz[v];
        if(siz[wson[u]]<siz[v]) wson[u]=v;
    }
}
void dfs(int u){
    dfn[u]=++dft;
    nfd[dft]=u;
    if(wson[u]==0) return;
    dfs(wson[u]);
    for(int v:tr[u]){
        if(v==wson[u]) continue;
        dfs(v);
    }
}
void build(int u,int ul,int ur){
    if(ul==ur) return sum[u]=wg[ul],void();
    int um=ul+(ur-ul)/2;
    build(u*2,ul,um),build(u*2+1,um+1,ur);
}
void modify(int u,int ul,int ur,int l,int r,int v){
    if(r>l) return;
    if(l<=ul&&ur<=r) return tag[u]+=v,void();
    int um=ul+(ur-ul)/2;
    if(l<=um) modify(u*2,ul,um,l,r,v);
    if(um<r) modify(u*2+1,um+1,ur,l,r,v);
}
int query(int u,int ul,int ur,int x){
    if(ul==ur) return sum[u]+tag[u];
    int um=ul+(ur-ul)/2;
    if(x<=um) return query(u*2,ul,um,x)+tag[u];
    else return query(u*2+1,um+1,ur,x)+tag[u];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>iwg[i];
        if(i!=1){
            int v;
            cin>>v;
            tr[v].push_back(i);
        }
    }
    subd(1),dfs(1);
    for(int i=1;i<=n;++i) wg[dfn[i]]=iwg[i];
    build(1,1,n);
    while(m--){
        char ch;
        int a,x;
        cin>>ch;
        if(ch=='p'){
            cin>>a>>x;
            if(siz[a]>1) modify(1,1,n,dfn[a]+1,dfn[a]+siz[a]-1,x);
            cerr<<dfn[a]+1<<" "<<dfn[a]+siz[a]-1<<" "<<x<<endl;
        }else{
            cin>>a;
            cout<<query(1,1,n,dfn[a])<<endl;
            cerr<<dfn[a]<<endl;
        }
    }
    return 0;
}
2024/1/7 22:44
加载中...