SyntaxPilot
Courses/Competitive Programming/Lesson 54
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 54 of 90

Euler tour and subtree queries

queued

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

  1. 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.
  2. 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).
  3. How do you support subtree sum queries with point updates? A Fenwick tree or segment tree indexed by tin: O(log n) each.
  4. 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).
  5. What are tin and tout? Entry and exit times of the DFS. With entry times only, tout[v] = tin[v] + sz[v] − 1.
  6. Why use an iterative DFS? A chain of 2 · 10^5 vertices makes recursion 2 · 10^5 calls deep, which can overflow the stack.
  7. What does i & -i compute? The lowest set bit of i (two's complement), the length of the block that bit[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]), then a[v] = x; indexing by v prints 24 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