These are the notes for Competitive Programming episode 54. The Euler tour (here: the order in which a depth-first walk first reaches each vertex) turns a tree into an array in which every subtree is one contiguous block. Team Totals asks for the total sales of an employee's whole team 2 · 10^5 times: walking the team every time is correct but Time Limit Exceeded on a long chain. Handing out badge numbers in visiting order gives each employee an entry time tin[v], and v's team is exactly the badges tin[v] … tin[v] + sz[v] − 1, so prefix sums answer every question in O(1). Subtracting pre[tin[v]] instead of pre[tin[v] − 1] drops the manager and prints 21 8 6 0 40 where 24 16 8 9 45 is right. Boss Check decides "is u an ancestor of v?" in O(1) with two comparisons. Live Sales Board adds updates: rebuilding the prefix sums is TLE, a Fenwick tree over the badge positions makes every operation O(log n), and updating at index v instead of tin[v] prints 24 16 16 37 where 24 24 8 37 is right. A stress test passes. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
HR walks the org chart to hand out ID badges. They visit a manager, then go through that manager's first team completely, then the next team, and so on, giving each person the next badge number at the moment they first reach them. Because HR never leaves a team until everyone in it has a badge, every team ends up with a block of consecutive badge numbers, starting at its manager's own badge and as long as the team. "Total sales of Priya's team" becomes "total sales of badges 2 to 6": a question about a range of an array.
Problem E1 · Team Totals
(Written for this course, in the style of a Codeforces Div. 2 problem.)
A company has n employees. Employee 1 is the CEO; every other employee v reports to one manager p_v. Employee v has sales a_v. Answer q questions: the total sales of v's team, meaning v and everyone below v (the subtree of v).
- Input: n q (1 ≤ n, q ≤ 2 · 10^5), then a_1 … a_n (0 ≤ a_v ≤ 10^9), then p_2 … p_n, then q lines v.
- Output: one total per line (up to 2 · 10^14, so
long long).
9 5
5 3 8 2 4 1 7 6 9
1 1 2 2 3 3 4 5
2
3
4
9
1
1 (5)
/ \
2 (3) 3 (8)
/ \ / \
4 (2) 5 (4) 6 (1) 7 (7)
| |
8 (6) 9 (9)
| Question | Team | Total |
|---|---|---|
2 |
2, 4, 8, 5, 9 | 3 + 2 + 6 + 4 + 9 = 24 |
3 |
3, 6, 7 | 16 |
4 |
4, 8 | 8 |
9 |
9 | 9 |
1 |
everyone | 45 |
The obvious attempt: walk the team (TLE)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
ll a[200001], pre[200001];
vector<int> ch[200001]; // the people each one manages
ll team(int v) { // walk the whole team
ll s = 0;
vector<int> st = {v};
while (!st.empty()) {
int x = st.back();
st.pop_back();
s += a[x];
for (int c : ch[x]) st.push_back(c);
}
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
while (q--) {
int v;
cin >> v;
cout << team(v) << "\n";
}
}
24
16
8
9
45
On a chain of command 2 · 10^5 long, questions about people near the top walk almost everyone:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
ll a[200001], pre[200001];
vector<int> ch[200001]; // the people each one manages
ll team(int v) { // walk the whole team
ll s = 0;
vector<int> st = {v};
while (!st.empty()) {
int x = st.back();
st.pop_back();
s += a[x];
for (int c : ch[x]) st.push_back(c);
}
return s;
}
int main() {
n = 200000; // one long chain of command
for (int v = 1; v <= n; v++) a[v] = v;
for (int v = 2; v <= n; v++) {
par[v] = v - 1;
ch[v - 1].push_back(v);
}
ll sum = 0;
for (int i = 0; i < 200000; i++) // 2·10^5 queries, big teams
sum += team(1 + i % 1000);
cout << sum << "\n";
}
Time Limit Exceeded (stopped after 8 seconds)
Badges in visiting order
A stack walk from the CEO: pop v, give it the next badge (tin[v] = ++timer), remember who has that badge (order[timer] = v), and push v's children in reverse, so the first child comes out first. The walk is a depth-first search: it finishes everything below a child before it moves to the next child.
For the sample the badges are:
| Badge | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| Employee | 1 | 2 | 4 | 8 | 5 | 9 | 3 | 6 | 7 |
| Sales | 5 | 3 | 2 | 6 | 4 | 9 | 8 | 1 | 7 |
Then the team sizes sz[v], children before parents (backwards through the badge order, exactly like episode 52). The team of v is badges tin[v] … tin[v] + sz[v] − 1: 2's team is badges 2 … 6, 3's team is badges 7 … 9. With prefix sums over the sales in badge order, pre[t] = pre[t − 1] + a[order[t]], a team total is
pre[tin[v] + sz[v] − 1] − pre[tin[v] − 1]
The off-by-one
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
ll a[200001], pre[200001];
vector<int> ch[200001]; // the people each one manages
void tour() { // badge numbers in visiting order
int timer = 0;
vector<int> st = {1};
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = ++timer;
order[timer] = v;
st.insert(st.end(), ch[v].rbegin(), ch[v].rend()); // children in order
}
for (int t = n; t >= 1; t--) { // children before parents
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
tour();
for (int t = 1; t <= n; t++) pre[t] = pre[t - 1] + a[order[t]];
while (q--) {
int v;
cin >> v;
cout << pre[tin[v] + sz[v] - 1] - pre[tin[v]] << "\n";
}
}
21
8
6
0
40
Every total is short by exactly the manager's own sales (24 − 3 = 21): pre[tin[v]] already contains badge tin[v], so subtracting it removes the manager. The block starts at tin[v], so subtract pre[tin[v] − 1].
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
ll a[200001], pre[200001];
vector<int> ch[200001]; // the people each one manages
void tour() { // badge numbers in visiting order
int timer = 0;
vector<int> st = {1};
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = ++timer;
order[timer] = v;
st.insert(st.end(), ch[v].rbegin(), ch[v].rend()); // children in order
}
for (int t = n; t >= 1; t--) { // children before parents
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
tour();
for (int t = 1; t <= n; t++) pre[t] = pre[t - 1] + a[order[t]];
while (q--) {
int v;
cin >> v;
cout << pre[tin[v] + sz[v] - 1] - pre[tin[v] - 1] << "\n"; // block of v
}
}
24
16
8
9
45
42
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
ll a[200001], pre[200001];
vector<int> ch[200001]; // the people each one manages
void tour() { // badge numbers in visiting order
int timer = 0;
vector<int> st = {1};
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = ++timer;
order[timer] = v;
st.insert(st.end(), ch[v].rbegin(), ch[v].rend()); // children in order
}
for (int t = n; t >= 1; t--) { // children before parents
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
int main() {
n = 200000; // one long chain of command
for (int v = 1; v <= n; v++) a[v] = v;
for (int v = 2; v <= n; v++) {
par[v] = v - 1;
ch[v - 1].push_back(v);
}
tour();
for (int t = 1; t <= n; t++) pre[t] = pre[t - 1] + a[order[t]];
ll sum = 0;
for (int i = 0; i < 200000; i++) {
int v = 1 + i % 1000;
sum += pre[tin[v] + sz[v] - 1] - pre[tin[v] - 1];
}
cout << sum << "\n";
}
3999986666700000
Problem E2 · Boss Check
(Written for this course; it is homework 2 of episode 53.)
Same company input; each question u v asks whether u is above v, i.e. an ancestor of v (everyone counts as their own ancestor). Print YES or NO.
u is an ancestor of v exactly when v is in u's team, so v's badge lies inside u's block:
tin[u] <= tin[v] && tin[v] < tin[u] + sz[u]
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
ll a[200001], pre[200001];
vector<int> ch[200001]; // the people each one manages
void tour() { // badge numbers in visiting order
int timer = 0;
vector<int> st = {1};
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = ++timer;
order[timer] = v;
st.insert(st.end(), ch[v].rbegin(), ch[v].rend()); // children in order
}
for (int t = n; t >= 1; t--) { // children before parents
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
bool above(int u, int v) { // is u an ancestor of v?
return tin[u] <= tin[v] && tin[v] < tin[u] + sz[u];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
tour();
while (q--) {
int u, v;
cin >> u >> v;
cout << (above(u, v) ? "YES" : "NO") << "\n";
}
}
YES
NO
YES
NO
YES
Problem E3 · Live Sales Board
(Written for this course.)
Same company, but sales change: 1 v x sets a_v = x, and 2 v asks for v's team total. n, q ≤ 2 · 10^5.
9 5
5 3 8 2 4 1 7 6 9
1 1 2 2 3 3 4 5
2 2
1 3 0
2 2
2 3
2 1
Rebuilding prefix sums (TLE)
One change to one badge changes every prefix after it. Rebuilding the whole prefix array after every update costs O(n):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
ll a[200001], pre[200001];
vector<int> ch[200001]; // the people each one manages
void tour() { // badge numbers in visiting order
int timer = 0;
vector<int> st = {1};
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = ++timer;
order[timer] = v;
st.insert(st.end(), ch[v].rbegin(), ch[v].rend()); // children in order
}
for (int t = n; t >= 1; t--) { // children before parents
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
int main() {
n = 200000; // one long chain of command
for (int v = 1; v <= n; v++) a[v] = v;
for (int v = 2; v <= n; v++) {
par[v] = v - 1;
ch[v - 1].push_back(v);
}
tour();
for (int t = 1; t <= n; t++) pre[t] = pre[t - 1] + a[order[t]];
ll sum = 0;
for (int i = 0; i < 200000; i++) {
int v = 1 + i % 1000;
if (i % 2 == 0) { // update: rebuild all prefix sums
a[v] = i;
for (int t = 1; t <= n; t++) pre[t] = pre[t - 1] + a[order[t]];
} else sum += pre[tin[v] + sz[v] - 1] - pre[tin[v] - 1];
}
cout << sum << "\n";
}
Time Limit Exceeded (stopped after 8 seconds)
The Fenwick tree
A Fenwick tree (binary indexed tree) keeps an array bit[1..n] where bit[i] holds the sum of the last i & −i positions ending at i (i & −i is the lowest set bit of i: 8 & −8 = 8, 6 & −6 = 2, 7 & −7 = 1).
| Box | Covers |
|---|---|
| bit[1] | 1 |
| bit[2] | 1 … 2 |
| bit[3] | 3 |
| bit[4] | 1 … 4 |
| bit[5] | 5 |
| bit[6] | 5 … 6 |
| bit[7] | 7 |
| bit[8] | 1 … 8 |
prefix(i)adds boxes while removing the lowest bit: prefix(7) = bit[7] + bit[6] + bit[4].add(i, x)adds x to every box that contains position i, moving up by the lowest bit: add at 5 touches bit[5], bit[6], bit[8].
Both visit at most log₂ n + 1 boxes. Episode 63 covers more Fenwick tricks. Here, every employee's sales go into the Fenwick tree at their badge, and an update adds the difference x − a_v.
Indexing by the employee instead of the badge
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
ll a[200001], pre[200001];
vector<int> ch[200001]; // the people each one manages
void tour() { // badge numbers in visiting order
int timer = 0;
vector<int> st = {1};
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = ++timer;
order[timer] = v;
st.insert(st.end(), ch[v].rbegin(), ch[v].rend()); // children in order
}
for (int t = n; t >= 1; t--) { // children before parents
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
ll bit[200001]; // Fenwick tree over badge positions
void add(int i, ll x) {
for (; i <= n; i += i & -i) bit[i] += x;
}
ll prefix(int i) {
ll s = 0;
for (; i > 0; i -= i & -i) s += bit[i];
return s;
}
ll subtree(int v) {
return prefix(tin[v] + sz[v] - 1) - prefix(tin[v] - 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
tour();
for (int v = 1; v <= n; v++) add(tin[v], a[v]);
while (q--) {
int type, v;
cin >> type >> v;
if (type == 1) {
ll x;
cin >> x;
add(v, x - a[v]); // change by the difference
a[v] = x;
} else cout << subtree(v) << "\n";
}
}
24
16
16
37
Setting employee 3's sales to 0 must not change 2's team, but 24 became 16: add(v, …) changed position 3, which is the badge of employee 4, inside 2's team. Employee 3 has badge 7.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
ll a[200001], pre[200001];
vector<int> ch[200001]; // the people each one manages
void tour() { // badge numbers in visiting order
int timer = 0;
vector<int> st = {1};
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = ++timer;
order[timer] = v;
st.insert(st.end(), ch[v].rbegin(), ch[v].rend()); // children in order
}
for (int t = n; t >= 1; t--) { // children before parents
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
ll bit[200001]; // Fenwick tree over badge positions
void add(int i, ll x) {
for (; i <= n; i += i & -i) bit[i] += x;
}
ll prefix(int i) {
ll s = 0;
for (; i > 0; i -= i & -i) s += bit[i];
return s;
}
ll subtree(int v) {
return prefix(tin[v] + sz[v] - 1) - prefix(tin[v] - 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
tour();
for (int v = 1; v <= n; v++) add(tin[v], a[v]);
while (q--) {
int type, v;
cin >> type >> v;
if (type == 1) {
ll x;
cin >> x;
add(tin[v], x - a[v]); // v lives at badge tin[v]
a[v] = x;
} else cout << subtree(v) << "\n";
}
}
24
24
8
37
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
ll a[200001], pre[200001];
vector<int> ch[200001]; // the people each one manages
void tour() { // badge numbers in visiting order
int timer = 0;
vector<int> st = {1};
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = ++timer;
order[timer] = v;
st.insert(st.end(), ch[v].rbegin(), ch[v].rend()); // children in order
}
for (int t = n; t >= 1; t--) { // children before parents
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
ll bit[200001]; // Fenwick tree over badge positions
void add(int i, ll x) {
for (; i <= n; i += i & -i) bit[i] += x;
}
ll prefix(int i) {
ll s = 0;
for (; i > 0; i -= i & -i) s += bit[i];
return s;
}
ll subtree(int v) {
return prefix(tin[v] + sz[v] - 1) - prefix(tin[v] - 1);
}
int main() {
n = 200000; // one long chain of command
for (int v = 1; v <= n; v++) a[v] = v;
for (int v = 2; v <= n; v++) {
par[v] = v - 1;
ch[v - 1].push_back(v);
}
tour();
for (int v = 1; v <= n; v++) add(tin[v], a[v]);
ll sum = 0;
for (int i = 0; i < 200000; i++) {
int v = 1 + i % 1000;
if (i % 2 == 0) { // update: log n
add(tin[v], i - a[v]);
a[v] = i;
} else sum += subtree(v); // query: log n
}
cout << sum << "\n";
}
2002450983274750
Stress test against walking the team
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
ll a[200001], pre[200001];
vector<int> ch[200001]; // the people each one manages
void tour() { // badge numbers in visiting order
int timer = 0;
vector<int> st = {1};
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = ++timer;
order[timer] = v;
st.insert(st.end(), ch[v].rbegin(), ch[v].rend()); // children in order
}
for (int t = n; t >= 1; t--) { // children before parents
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
ll bit[200001]; // Fenwick tree over badge positions
void add(int i, ll x) {
for (; i <= n; i += i & -i) bit[i] += x;
}
ll prefix(int i) {
ll s = 0;
for (; i > 0; i -= i & -i) s += bit[i];
return s;
}
ll subtree(int v) {
return prefix(tin[v] + sz[v] - 1) - prefix(tin[v] - 1);
}
ll team(int v) { // walk the whole team
ll s = 0;
vector<int> st = {v};
while (!st.empty()) {
int x = st.back();
st.pop_back();
s += a[x];
for (int c : ch[x]) st.push_back(c);
}
return s;
}
int main() {
mt19937 rng(54);
for (int t = 1; t <= 500; t++) {
n = rng() % 10 + 1;
for (int v = 1; v <= n; v++) ch[v].clear(), sz[v] = 0, bit[v] = 0, a[v] = rng() % 100;
for (int v = 2; v <= n; v++) { // random company
par[v] = rng() % (v - 1) + 1;
ch[par[v]].push_back(v);
}
tour();
for (int v = 1; v <= n; v++) add(tin[v], a[v]);
for (int k = 0; k < 20; k++) { // 20 random operations
int v = rng() % n + 1;
if (rng() % 2) {
ll x = rng() % 100;
add(tin[v], x - a[v]);
a[v] = x;
} else if (subtree(v) != team(v)) {
cout << "mismatch on test " << t;
return 0;
}
}
}
cout << "all 500 tests passed";
}
all 500 tests passed
Complexity vs the constraints
| Method | Preparation | Per question | Per update | Verdict at n, q = 2 · 10^5 |
|---|---|---|---|---|
| walk the team | none | O(team size), up to O(n) | O(1) | TLE |
| Euler tour + prefix sums | O(n) | O(1) | rebuild O(n) | accepted without updates, TLE with them |
| ancestor check with tin and sz | O(n) | O(1) | none | accepted |
| Euler tour + Fenwick tree | O(n log n) | O(log n) | O(log n) | accepted (a few million steps) |
Memory is O(n) for all of them: a few arrays of 2 · 10^5 values.
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| walking the team for every question | Time Limit Exceeded |
O(n) per question | Euler tour |
pre[tin[v] + sz[v] - 1] - pre[tin[v]] |
21 8 6 0 40 (expected 24 16 8 9 45) |
drops badge tin[v], the manager | - pre[tin[v] - 1] |
add(v, x - a[v]) |
24 16 16 37 (expected 24 24 8 37) |
v is not its badge | add(tin[v], x - a[v]) |
add(tin[v], x) instead of the difference |
the old sales are still counted | the Fenwick tree adds, it does not replace | add x - a[v], then set a[v] = x |
forgetting a[v] = x after an update |
the next update of v is wrong | the difference is taken from a stale value | keep a[] up to date |
| rebuilding prefix sums on every update | Time Limit Exceeded |
O(n) per update | Fenwick tree |
| recursive DFS on a 2 · 10^5 chain | Runtime Error (stack overflow) | 2 · 10^5 nested calls | your own stack |
| Fenwick tree starting at index 0 | infinite loop in add |
0 & −0 = 0, i never grows | positions start at 1 |
team totals in int |
wrapped totals | up to 2 · 10^14 | long long |
Mini project
Build a subtree query kit for a rooted tree: tour(), inTeam(u, v), teamSum(v) with prefix sums, and a version with a Fenwick tree that supports setValue(v, x). Add teamMax(v) with a sparse table (homework 3) and addToTeam(v, x) with a Fenwick tree over differences (homework 2). Test it on a chain, a star and random trees for n = 10, 1000 and 2 · 10^5; check the small ones against walking the team and time the big ones.
Practice
These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17).
1. Count the employees with sales ≥ k in a team. Company input; each question v k prints how many people in v's team have sales at least k.
Solution
Offline: answer the questions in decreasing order of k. Sort the employees by sales, biggest first, and before each question add a 1 at the badge of every employee whose sales are ≥ k. Then the question is a Fenwick range sum over v's block. O((n + q) log n).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
vector<int> ch[200001];
void tour() {
int timer = 0;
vector<int> st = {1};
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = ++timer;
order[timer] = v;
st.insert(st.end(), ch[v].rbegin(), ch[v].rend());
}
for (int t = n; t >= 1; t--) {
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
ll a[200001], bit[200001];
void add(int i, ll x) { for (; i <= n; i += i & -i) bit[i] += x; }
ll prefix(int i) { ll s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
tour();
vector<array<ll, 3>> qs(q); // (k, v, index)
for (int i = 0; i < q; i++) cin >> qs[i][1] >> qs[i][0], qs[i][2] = i;
sort(qs.rbegin(), qs.rend()); // biggest k first
vector<int> people(n);
iota(people.begin(), people.end(), 1);
sort(people.begin(), people.end(), [](int x, int y) { return a[x] > a[y]; });
vector<ll> ans(q);
int j = 0;
for (auto [k, v, i] : qs) {
while (j < n && a[people[j]] >= k) add(tin[people[j++]], 1); // everyone with sales >= k
ans[i] = prefix(tin[v] + sz[v] - 1) - prefix(tin[v] - 1);
}
for (ll x : ans) cout << x << "\n";
}
3
4
2
0
2. Add x to every sale in a team. Company input; 1 v x adds x to the sales of everyone in v's team, 2 v prints employee v's sales.
Solution
A range update with point queries: keep a Fenwick tree over differences. Adding x to badges tin[v] … tin[v] + sz[v] − 1 is add(tin[v], x) and add(tin[v] + sz[v], −x); the extra amount at badge t is prefix(t).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
vector<int> ch[200001];
void tour() {
int timer = 0;
vector<int> st = {1};
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = ++timer;
order[timer] = v;
st.insert(st.end(), ch[v].rbegin(), ch[v].rend());
}
for (int t = n; t >= 1; t--) {
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
ll a[200001], bit[200001]; // Fenwick over DIFFERENCES
void add(int i, ll x) { for (; i <= n; i += i & -i) bit[i] += x; }
ll prefix(int i) { ll s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
tour();
while (q--) {
int type, v;
cin >> type >> v;
if (type == 1) { // add x to the whole block of v
ll x;
cin >> x;
add(tin[v], x);
add(tin[v] + sz[v], -x);
} else cout << a[v] + prefix(tin[v]) << "\n"; // one person's sales
}
}
19
8
20
3. The best salesperson in a team (no updates). Company input; each question v prints the largest sales in v's team.
Solution
A sparse table over the badge order answers range maximum in O(1): sp[k][t] is the maximum of badges t … t + 2^k − 1, and a range is covered by two overlapping blocks of the same power of two.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
vector<int> ch[200001];
void tour() {
int timer = 0;
vector<int> st = {1};
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = ++timer;
order[timer] = v;
st.insert(st.end(), ch[v].rbegin(), ch[v].rend());
}
for (int t = n; t >= 1; t--) {
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
int a[200001], sp[18][200001]; // sparse table over badge order
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
tour();
for (int t = 1; t <= n; t++) sp[0][t] = a[order[t]];
for (int k = 1; (1 << k) <= n; k++)
for (int t = 1; t + (1 << k) - 1 <= n; t++)
sp[k][t] = max(sp[k - 1][t], sp[k - 1][t + (1 << (k - 1))]);
while (q--) {
int v;
cin >> v;
int l = tin[v], r = tin[v] + sz[v] - 1, k = __lg(r - l + 1);
cout << max(sp[k][l], sp[k][r - (1 << k) + 1]) << "\n"; // two overlapping blocks
}
}
9
8
6
9
4. Sums along a route, with updates. Company input; 1 x y sets a_x = y, 2 x y prints the total sales of the people on the route from x to y (both included).
Solution
Let rootSum(v) be the total sales from the CEO down to v. Changing a_v changes rootSum for everyone in v's team: a range update over v's block, done with a Fenwick tree over differences. Then with the LCA l of x and y (episode 53), the route total is rootSum(x) + rootSum(y) − 2 · rootSum(l) + a_l.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
vector<int> ch[200001];
void tour() {
int timer = 0;
vector<int> st = {1};
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = ++timer;
order[timer] = v;
st.insert(st.end(), ch[v].rbegin(), ch[v].rend());
}
for (int t = n; t >= 1; t--) {
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
const int LOG = 18;
int up[LOG][200001], dep[200001];
ll a[200001], bit[200001]; // differences: point query = root-path sum
void add(int i, ll x) { for (; i <= n; i += i & -i) bit[i] += x; }
ll prefix(int i) { ll s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }
void addTeam(int v, ll x) { add(tin[v], x); add(tin[v] + sz[v], -x); }
ll rootSum(int v) { return prefix(tin[v]); } // sales from the CEO down to v
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int k = 0; k < LOG; k++) if ((dep[u] - dep[v]) >> k & 1) u = up[k][u];
if (u == v) return u;
for (int k = LOG - 1; k >= 0; k--)
if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
return up[0][u];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
tour();
up[0][1] = 1;
for (int t = 2; t <= n; t++) { // badge order: parents first
int v = order[t];
up[0][v] = par[v], dep[v] = dep[par[v]] + 1;
}
for (int k = 1; k < LOG; k++)
for (int v = 1; v <= n; v++) up[k][v] = up[k - 1][up[k - 1][v]];
for (int v = 1; v <= n; v++) addTeam(v, a[v]); // a[v] counts for everyone below v
while (q--) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) addTeam(x, y - a[x]), a[x] = y;
else {
int l = lca(x, y);
cout << rootSum(x) + rootSum(y) - 2 * rootSum(l) + a[l] << "\n";
}
}
}
24
25
21
Quick quiz
u has badge 3 and a team of size 4. v has badge 7. Is u an ancestor of v?
tin[u] <= tin[v] && tin[v] < tin[u] + sz[u]
A) Yes · B) No · C) Only if v is a leaf · D) Can't tell
Answer
B. u's block is badges 3, 4, 5 and 6. Badge 7 is just outside it (7 < 3 + 4 is false), so v is not in u's team.
Interview questions
- What is an Euler tour of a tree, and why is it useful? The order in which a DFS first visits the vertices (entry times). Every subtree becomes a contiguous range [tin[v], tin[v] + sz[v] − 1], so subtree queries become range queries on an array.
- How do you check whether u is an ancestor of v in O(1)? tin[u] ≤ tin[v] < tin[u] + sz[u] (or tin[u] ≤ tin[v] and tout[v] ≤ tout[u] with exit times).
- How do you support subtree sum queries with point updates? A Fenwick tree or segment tree indexed by tin: O(log n) each.
- How do you add x to a whole subtree? A range update on [tin[v], tin[v] + sz[v] − 1]: a Fenwick tree over differences (point query) or a lazy segment tree (range sum).
- What are tin and tout? Entry and exit times of the DFS. With entry times only, tout[v] = tin[v] + sz[v] − 1.
- Why use an iterative DFS? A chain of 2 · 10^5 vertices makes recursion 2 · 10^5 calls deep, which can overflow the stack.
- What does
i & -icompute? The lowest set bit of i (two's complement), the length of the block thatbit[i]covers.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Rooted tree | A tree with one vertex chosen as the top | the company, rooted at the CEO |
| Subtree (team) | A vertex and everyone below it | the team of 2 is {2, 4, 8, 5, 9} |
Subtree size sz[v] |
The number of vertices in v's subtree | sz[2] = 5 |
| Ancestor | A vertex on the way from v up to the root, including v | 1 and 2 are ancestors of 9 |
| DFS (depth-first search) | A walk that finishes everything below a child before moving to the next child | the badge walk |
| Iterative DFS | A DFS with its own stack instead of recursion | vector<int> st = {1}; |
| Euler tour (DFS order) | The vertices in the order a DFS first reaches them | 1 2 4 8 5 9 3 6 7 |
Entry time tin[v] |
v's position in the Euler tour (its badge) | tin[3] = 7 |
Exit time tout[v] |
The last badge in v's subtree: tin[v] + sz[v] − 1 | tout[2] = 6 |
order[t] |
The vertex with badge t | order[7] = 3 |
| Flattening | Turning a tree into an array so subtrees are ranges | the badge table |
| Prefix sums | pre[t] = sum of the first t values; a range sum is pre[r] − pre[l − 1] |
episode 7 |
| Off-by-one error | A bug where an index is one too big or too small | pre[tin[v]] |
| Point update | Changing one value | 1 v x |
| Range query | Asking about a block of consecutive positions | a team total |
| Fenwick tree (binary indexed tree) | An array of block sums supporting point update and prefix sum in O(log n) | add, prefix |
Lowest set bit i & -i |
The smallest power of two in i's binary form | 6 & −6 = 2 |
| Difference array | Storing changes at the start and end of a range, so a prefix gives the value | homework 2 |
| Sparse table | Precomputed maxima of blocks of length 2^k; O(1) range max | homework 3 |
| Offline processing | Reading all questions first and answering them in a convenient order | homework 1 |
| LCA | The deepest common ancestor of two vertices | episode 53 |
| Stress test | Comparing a fast solution with a slow, surely-correct one on many random inputs | all 500 tests passed |
| O(1), O(log n), O(n) | Constant, logarithmic, linear time | prefix sums, Fenwick, walking |
| Time Limit Exceeded (TLE) | The program is too slow | walking the team |
| Wrong Answer (WA) | The program prints a wrong output | 21 8 6 0 40 |
long long |
64-bit integer | team totals |
Summary
- Badges in DFS visiting order (
tin[v]) put every subtree in one block: tin[v] … tin[v] + sz[v] − 1. - Walk with your own stack, push children in reverse to keep their order, and get sizes children before parents.
- Team total =
pre[tin[v] + sz[v] − 1] − pre[tin[v] − 1];pre[tin[v]]drops the manager (21 8 6 0 40). - u is an ancestor of v ⇔ tin[u] ≤ tin[v] < tin[u] + sz[u]: O(1).
- With updates, a Fenwick tree over badges:
add(tin[v], x − a[v]), thena[v] = x; indexing by v prints24 16 16 37. - Walking: O(n) per question. Tour + prefix sums: O(1). Tour + Fenwick: O(log n) per operation.
Solutions in C++, Java and Python
Problem E1 · Team Totals
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
ll a[200001], pre[200001];
vector<int> ch[200001]; // the people each one manages
void tour() { // badge numbers in visiting order
int timer = 0;
vector<int> st = {1};
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = ++timer;
order[timer] = v;
st.insert(st.end(), ch[v].rbegin(), ch[v].rend()); // children in order
}
for (int t = n; t >= 1; t--) { // children before parents
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
tour();
for (int t = 1; t <= n; t++) pre[t] = pre[t - 1] + a[order[t]];
while (q--) {
int v;
cin >> v;
cout << pre[tin[v] + sz[v] - 1] - pre[tin[v] - 1] << "\n"; // block of v
}
}
Java
import java.io.*;
import java.util.*;
public class Main {
static int n;
static int[] par, tin, sz, order, head, next;
static long[] a;
static void tour() { // badges in visiting order, own stack
int timer = 0, top = 0;
int[] st = new int[n + 1];
st[top++] = 1;
while (top > 0) {
int v = st[--top];
tin[v] = ++timer;
order[timer] = v;
for (int c = head[v]; c != 0; c = next[c]) st[top++] = c; // any child order works
}
for (int t = n; t >= 1; t--) { // children before parents
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
static void read(DataInputStream in) throws IOException {
par = new int[n + 1]; tin = new int[n + 1]; sz = new int[n + 1]; order = new int[n + 1];
head = new int[n + 1]; next = new int[n + 1]; a = new long[n + 1];
for (int v = 1; v <= n; v++) a[v] = nextInt(in);
for (int v = 2; v <= n; v++) {
par[v] = nextInt(in);
next[v] = head[par[v]];
head[par[v]] = v;
}
}
static int nextInt(DataInputStream in) throws IOException {
int r = 0, b = in.read();
while (b < '0') b = in.read();
while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
return r;
}
public static void main(String[] args) throws IOException {
DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
n = nextInt(in);
int q = nextInt(in);
read(in);
tour();
long[] pre = new long[n + 1];
for (int t = 1; t <= n; t++) pre[t] = pre[t - 1] + a[order[t]];
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
int v = nextInt(in);
sb.append(pre[tin[v] + sz[v] - 1] - pre[tin[v] - 1]).append('\n');
}
System.out.print(sb);
}
}
24
16
8
9
45
Python
import sys
def read_company(data):
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:n + 2]]
par = [0, 0] + [int(x) for x in data[n + 2:2 * n + 1]]
ch = [[] for _ in range(n + 1)]
for v in range(2, n + 1):
ch[par[v]].append(v)
tin, sz, order = [0] * (n + 1), [0] * (n + 1), [0] * (n + 1)
timer, st = 0, [1]
while st: # badges in visiting order, own stack
v = st.pop()
timer += 1
tin[v], order[timer] = timer, v
st.extend(reversed(ch[v])) # children in order
for t in range(n, 0, -1): # children before parents
v = order[t]
sz[v] += 1
if v != 1:
sz[par[v]] += sz[v]
return n, q, a, tin, sz, order, 2 * n + 1 # the last value: where the queries start
def main():
data = sys.stdin.buffer.read().split()
n, q, a, tin, sz, order, pos = read_company(data)
pre = [0] * (n + 1)
for t in range(1, n + 1):
pre[t] = pre[t - 1] + a[order[t]]
out = []
for i in range(q):
v = int(data[pos + i])
out.append(pre[tin[v] + sz[v] - 1] - pre[tin[v] - 1])
print("\n".join(map(str, out)))
main()
24
16
8
9
45
Problem E2 · Boss Check
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
ll a[200001], pre[200001];
vector<int> ch[200001]; // the people each one manages
void tour() { // badge numbers in visiting order
int timer = 0;
vector<int> st = {1};
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = ++timer;
order[timer] = v;
st.insert(st.end(), ch[v].rbegin(), ch[v].rend()); // children in order
}
for (int t = n; t >= 1; t--) { // children before parents
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
bool above(int u, int v) { // is u an ancestor of v?
return tin[u] <= tin[v] && tin[v] < tin[u] + sz[u];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
tour();
while (q--) {
int u, v;
cin >> u >> v;
cout << (above(u, v) ? "YES" : "NO") << "\n";
}
}
Java
import java.io.*;
import java.util.*;
public class Main {
static int n;
static int[] par, tin, sz, order, head, next;
static long[] a;
static void tour() { // badges in visiting order, own stack
int timer = 0, top = 0;
int[] st = new int[n + 1];
st[top++] = 1;
while (top > 0) {
int v = st[--top];
tin[v] = ++timer;
order[timer] = v;
for (int c = head[v]; c != 0; c = next[c]) st[top++] = c; // any child order works
}
for (int t = n; t >= 1; t--) { // children before parents
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
static void read(DataInputStream in) throws IOException {
par = new int[n + 1]; tin = new int[n + 1]; sz = new int[n + 1]; order = new int[n + 1];
head = new int[n + 1]; next = new int[n + 1]; a = new long[n + 1];
for (int v = 1; v <= n; v++) a[v] = nextInt(in);
for (int v = 2; v <= n; v++) {
par[v] = nextInt(in);
next[v] = head[par[v]];
head[par[v]] = v;
}
}
static int nextInt(DataInputStream in) throws IOException {
int r = 0, b = in.read();
while (b < '0') b = in.read();
while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
return r;
}
public static void main(String[] args) throws IOException {
DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
n = nextInt(in);
int q = nextInt(in);
read(in);
tour();
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
int u = nextInt(in), v = nextInt(in);
boolean above = tin[u] <= tin[v] && tin[v] < tin[u] + sz[u];
sb.append(above ? "YES" : "NO").append('\n');
}
System.out.print(sb);
}
}
YES
NO
YES
NO
YES
Python
import sys
def read_company(data):
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:n + 2]]
par = [0, 0] + [int(x) for x in data[n + 2:2 * n + 1]]
ch = [[] for _ in range(n + 1)]
for v in range(2, n + 1):
ch[par[v]].append(v)
tin, sz, order = [0] * (n + 1), [0] * (n + 1), [0] * (n + 1)
timer, st = 0, [1]
while st: # badges in visiting order, own stack
v = st.pop()
timer += 1
tin[v], order[timer] = timer, v
st.extend(reversed(ch[v])) # children in order
for t in range(n, 0, -1): # children before parents
v = order[t]
sz[v] += 1
if v != 1:
sz[par[v]] += sz[v]
return n, q, a, tin, sz, order, 2 * n + 1 # the last value: where the queries start
def main():
data = sys.stdin.buffer.read().split()
n, q, a, tin, sz, order, pos = read_company(data)
out = []
for i in range(q):
u, v = int(data[pos + 2 * i]), int(data[pos + 2 * i + 1])
out.append("YES" if tin[u] <= tin[v] < tin[u] + sz[u] else "NO")
print("\n".join(out))
main()
YES
NO
YES
NO
YES
Problem E3 · Live Sales Board
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, par[200001], tin[200001], sz[200001], order[200001];
ll a[200001], pre[200001];
vector<int> ch[200001]; // the people each one manages
void tour() { // badge numbers in visiting order
int timer = 0;
vector<int> st = {1};
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = ++timer;
order[timer] = v;
st.insert(st.end(), ch[v].rbegin(), ch[v].rend()); // children in order
}
for (int t = n; t >= 1; t--) { // children before parents
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
ll bit[200001]; // Fenwick tree over badge positions
void add(int i, ll x) {
for (; i <= n; i += i & -i) bit[i] += x;
}
ll prefix(int i) {
ll s = 0;
for (; i > 0; i -= i & -i) s += bit[i];
return s;
}
ll subtree(int v) {
return prefix(tin[v] + sz[v] - 1) - prefix(tin[v] - 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
tour();
for (int v = 1; v <= n; v++) add(tin[v], a[v]);
while (q--) {
int type, v;
cin >> type >> v;
if (type == 1) {
ll x;
cin >> x;
add(tin[v], x - a[v]); // v lives at badge tin[v]
a[v] = x;
} else cout << subtree(v) << "\n";
}
}
Java
import java.io.*;
import java.util.*;
public class Main {
static int n;
static int[] par, tin, sz, order, head, next;
static long[] a;
static void tour() { // badges in visiting order, own stack
int timer = 0, top = 0;
int[] st = new int[n + 1];
st[top++] = 1;
while (top > 0) {
int v = st[--top];
tin[v] = ++timer;
order[timer] = v;
for (int c = head[v]; c != 0; c = next[c]) st[top++] = c; // any child order works
}
for (int t = n; t >= 1; t--) { // children before parents
int v = order[t];
sz[v] += 1;
if (v != 1) sz[par[v]] += sz[v];
}
}
static void read(DataInputStream in) throws IOException {
par = new int[n + 1]; tin = new int[n + 1]; sz = new int[n + 1]; order = new int[n + 1];
head = new int[n + 1]; next = new int[n + 1]; a = new long[n + 1];
for (int v = 1; v <= n; v++) a[v] = nextInt(in);
for (int v = 2; v <= n; v++) {
par[v] = nextInt(in);
next[v] = head[par[v]];
head[par[v]] = v;
}
}
static int nextInt(DataInputStream in) throws IOException {
int r = 0, b = in.read();
while (b < '0') b = in.read();
while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
return r;
}
static long[] bit;
static void add(int i, long x) { for (; i <= n; i += i & -i) bit[i] += x; }
static long prefix(int i) { long s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }
public static void main(String[] args) throws IOException {
DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
n = nextInt(in);
int q = nextInt(in);
read(in);
tour();
bit = new long[n + 1];
for (int v = 1; v <= n; v++) add(tin[v], a[v]);
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
int type = nextInt(in), v = nextInt(in);
if (type == 1) {
long x = nextInt(in);
add(tin[v], x - a[v]);
a[v] = x;
} else sb.append(prefix(tin[v] + sz[v] - 1) - prefix(tin[v] - 1)).append('\n');
}
System.out.print(sb);
}
}
24
24
8
37
Python
import sys
def read_company(data):
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:n + 2]]
par = [0, 0] + [int(x) for x in data[n + 2:2 * n + 1]]
ch = [[] for _ in range(n + 1)]
for v in range(2, n + 1):
ch[par[v]].append(v)
tin, sz, order = [0] * (n + 1), [0] * (n + 1), [0] * (n + 1)
timer, st = 0, [1]
while st: # badges in visiting order, own stack
v = st.pop()
timer += 1
tin[v], order[timer] = timer, v
st.extend(reversed(ch[v])) # children in order
for t in range(n, 0, -1): # children before parents
v = order[t]
sz[v] += 1
if v != 1:
sz[par[v]] += sz[v]
return n, q, a, tin, sz, order, 2 * n + 1 # the last value: where the queries start
def main():
data = sys.stdin.buffer.read().split()
n, q, a, tin, sz, order, pos = read_company(data)
bit = [0] * (n + 1)
def add(i, x):
while i <= n:
bit[i] += x
i += i & -i
def prefix(i):
s = 0
while i > 0:
s += bit[i]
i -= i & -i
return s
for v in range(1, n + 1):
add(tin[v], a[v])
out = []
for _ in range(q):
if data[pos] == b"1":
v, x = int(data[pos + 1]), int(data[pos + 2])
pos += 3
add(tin[v], x - a[v])
a[v] = x
else:
v = int(data[pos + 1])
pos += 2
out.append(prefix(tin[v] + sz[v] - 1) - prefix(tin[v] - 1))
print("\n".join(map(str, out)))
main()
24
24
8
37