NC23051（华华和月月种树 ）

感受

思路

#include <bits/stdc++.h>
#define ls o << 1
#define rs o << 1 | 1
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int maxm = 4e5 + 10;
int lazy[maxn << 2];
struct edge{
    int v, nex;
}e[maxn << 1];
int n, m, in[maxn], out[maxn], tot;
int head[maxn], cnt;
vector<int> query[maxm];
void add_edge(int u, int v){
    e[cnt] = (edge){v, head[u]};
    head[u] = cnt++;
}
void init(){
    cnt = 0; n = 1e5 + 5;
    for(int i = 0; i <= n; i++){
        head[i] = -1;
    }
}
void dfs(int u, int fa){
    in[u] = ++tot;
    int v;
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v;
        if(v == fa) continue;
        dfs(v, u);
    }
    out[u] = tot;
}
void build(int o, int l, int r){
    if(l == r){
        lazy[o] = 0;
        return ;
    }
    int mid = (l + r) / 2;
    build(ls, l, mid);
    build(rs, mid + 1, r);
}
void push(int o){
    lazy[ls] += lazy[o];
    lazy[rs] += lazy[o];
    lazy[o] = 0;
}
void update(int o, int l, int r, int x, int y, int k){
    if(l >= x && y >= r){
        lazy[o] += k;
        return ;
    }
    push(o);
    int mid = (l + r) / 2;
    if(mid >= x) update(ls, l, mid, x, y, k);
    if(y > mid) update(rs, mid + 1, r, x, y, k);
}
void update1(int o, int l, int r, int x){
    if(l == r){
        lazy[o] = 0;
        return ;
    }
    push(o);
    int mid = (l + r) / 2;
    if(mid >= x){
        update1(ls, l, mid, x);
    }
    else{
        update1(rs, mid + 1, r, x);
    }
}
int qry(int o, int l, int r, int x){
    if(l == r){
        return lazy[o];
    }
    push(o);
    int mid = (l + r) / 2;
    if(mid >= x) return qry(ls, l, mid, x);
    else return qry(rs, mid + 1, r, x);
}
void print(){
    for(int i = 0; i < n; i++){
        printf("in[%d] = %d  out[%d] = %d\n", i, in[i], i, out[i]);
    }
}
int main(){
    scanf("%d", &m);
    int opt, x, y;
    init(); n = 0;
    for(int i = 1; i <= m; i++){
        scanf("%d", &opt);
        if(opt == 1){
            scanf("%d", &x); n++; add_edge(n, x); add_edge(x, n);
            query[i].push_back(1);
        }
        else if(opt == 2){
            scanf("%d%d", &x, &y);
            query[i].push_back(2); query[i].push_back(x); query[i].push_back(y);
        }
        else{
            scanf("%d", &x);
            query[i].push_back(3); query[i].push_back(x);
        }
    }
    dfs(0, -1); n = tot; tot = 0;
    //print();
    build(1, 1, n);
    for(int i = 1; i <= m; i++){
        if(query[i][0] == 1){
            tot++;
            update1(1, 1, n, in[tot]);
        }
        else if(query[i][0] == 2){
            int x, k; x = query[i][1]; k = query[i][2];
            update(1, 1, n, in[x], out[x], k);
        }
        else{
            int x = query[i][1];
            printf("%d\n", qry(1, 1, n, in[x]));
        }
    }
    return 0;
}