1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e5 + 10;
const ll mod = 1e9 + 7;
int m, c, n;
struct Q
{
int o, p, a;
};
Q q[N];
vector<int>G[N];
int dfn[N], L[N], R[N];
void dfs(int u) {
L[u] = R[u] = dfn[u] = ++n;
for (int v : G[u]) {
dfs(v);
L[u] = min(L[u], L[v]);
R[u] = max(R[u], R[v]);
}
}
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int tr[N << 2], laz[N << 2];
void up(int rt) {
tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
}
void down(int rt) {
int& x = laz[rt];
if (x) {
tr[rt << 1] += x;
tr[rt << 1 | 1] += x;
laz[rt << 1] += x;
laz[rt << 1 | 1] += x;
x = 0;
}
}
void upd(int x, int ql, int qr, int l, int r, int rt) {
if (ql <= l && qr >= r) {
laz[rt] += x;
tr[rt] += x;
return;
}
down(rt);
if (ql <= mid)upd(x, ql, qr, lson);
if (qr > mid)upd(x, ql, qr, rson);
up(rt);
}
int qry(int q, int l, int r, int rt) {
if (l == r)return tr[rt];
down(rt);
if (q <= mid)return qry(q, lson);
else return qry(q, rson);
}
int ad[N];
int main() {
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
int o, p, a;
scanf("%d", &o);
if (o == 1) {
scanf("%d", &p);
G[p].push_back(++c);
q[i] = Q{ o,p,c };
}
else if (o == 2) {
scanf("%d%d", &p, &a);
q[i] = Q{ o,p,a };
}
else {
scanf("%d", &p);
q[i] = Q{ o,p,-1 };
}
}
dfs(0);
for (int i = 1; i <= m; i++) {
int o = q[i].o, p = q[i].p, a = q[i].a;
if (o == 1) {
ad[a] = -qry(dfn[a], 1, n, 1);
}
else if (o == 2) {
upd(a, L[p], R[p], 1, n, 1);
}
else {
printf("%d\n", ad[p] + qry(dfn[p], 1, n, 1));
}
}
return 0;
}
|
