求助!第4,5点WA了
查看原帖
求助!第4,5点WA了
544458
WAI_kycm楼主2023/11/6 14:58
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e7 + 5;
int n, m;
int a[maxn];
struct Node {int to, next;} e[maxn];
int len, head[maxn];
void Insert(int u ,int v) {e[++len].to = v; e[len].next = head[u]; head[u] = len;}
int cnt, dfn[maxn], rk[maxn], siz[maxn], son[maxn], deep[maxn], f[maxn], top[maxn];
///////////////////////////////////////////////////////////////
void dfs1(int u){
    siz[u] = 1; deep[u] = deep[f[u]] + 1;
    for(int i = head[u]; i; i = e[i].next){
        int v = e[i].to;
        if(v == f[u]) continue;
        f[v] = u;
        dfs1(v);
        siz[u] += siz[v];
        if(!son[u] or siz[son[u]] < siz[v]) son[u] = v;
    }
}
void dfs2(int u, int fa){
    top[u] = fa;
    dfn[u] = ++cnt;
    rk[cnt] = u;
    if( son[u]) dfs2(son[u], fa);
    for(int i = head[u]; i; i = e[i].next){
        int v = e[i].to;
        if(v != f[u] and v != son[u]) dfs2(v, v);
    }
}
///////////////////////////////////////////////////////////////
int t[maxn], lazy[maxn];
void pushup(int rt) {t[rt] = t[rt << 1] + t[rt << 1 | 1];}
void pushdown(int rt, int ln, int rn){
    if( lazy[rt]){
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        t[rt << 1] += lazy[rt] * ln;
        t[rt << 1 | 1] += lazy[rt] * rn;
        lazy[rt] = 0;
    }
}
void build(int rt, int l, int r){
    if(l == r) {t[rt] = a[rk[l]]; return;}
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}
void update(int rt, int l, int r, int L, int R, int val){
    if(l > r) return;
    if(L <= l and r <= R){
        t[rt] += (r - l + 1) * val;
        lazy[rt] += val;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(rt, mid - l + 1, r - mid);
    if(L <= mid) update(rt << 1, l, mid, L, R, val);
    if(R > mid) update(rt << 1 | 1, mid + 1, r, L, R, val);
    pushup(rt);
}
int query(int rt, int l, int r, int x){
    if(l == r) return t[rt];
    int mid = (l + r) >> 1;
    pushdown(rt, mid - l + 1, r - mid);
    if(x <= mid) return query(rt << 1, l, mid, x);
    else return query(rt << 1 | 1, mid + 1, r, x);
}
///////////////////////////////////////////////////////////////
void Solve(){
    cin>>n>>m;
    cin>>a[1];
    for(int i = 2; i <= n; ++i) {int u; cin>>a[i]>>u; Insert(u, i); Insert(i, u);}
    dfs1(1); dfs2(1, 1); build(1, 1, n);
    while(m--){
        char ch; cin>>ch;
        if(ch == 'p'){
            int u, val; cin>>u>>val;
            update(1, 1, n, dfn[u] + 1, dfn[u] + siz[u] - 1, val);
        }else{
            int u; cin>>u;
            cout<<query(1, 1, n, dfn[u])<<endl;
        }
    }
}
int main(){
    Solve();
    return 0;
}
2023/11/6 14:58
加载中...