Overview

Given a boss-subordinate relationship represented as a tree, we efficiently process salary updates (point updates) and queries of the form “among a given employee’s subordinates, how many have a higher salary than them?” (subtree queries).

Analysis

Key Observation 1: The set of subordinates is a “subtree”

The subordinates of employee \(v\) correspond exactly to the subtree rooted at \(v\) in the rooted tree (excluding \(v\) itself).

By assigning each vertex an entry time \(tin[v]\) according to DFS visit order (Euler Tour), the vertices in the subtree of \(v\) form a contiguous interval on an array:

• Subtree (including \(v\) itself) → \([tin[v],\ tout[v]]\)
• Subordinates (excluding \(v\) itself) → \([tin[v]+1,\ tout[v]]\)

Therefore, the problem can be transformed into the following form:

Among the values in the array interval \([L,R]\), count the number of elements greater than a threshold \(T\) (where values can be updated).

Why a naive solution is difficult

• Iterating over all subordinates for each query 2 takes \(O(N)\) in the worst case, totaling \(O(NQ)\) which is on the order of \(10^{10}\) and results in TLE.
• To efficiently count “the number of elements \(>T\) in an interval,” we need a data structure that handles value comparisons.
• Furthermore, since there are update queries, static sorting or prefix sums alone cannot handle this.

Solution approach

To simultaneously handle range queries (on positions) and value comparisons, we use the classic technique of:

• A Fenwick Tree (BIT) where each node itself contains another Fenwick Tree (2D BIT)

However, since values \(A_i\) can be as large as \(10^9\), we apply coordinate compression per BIT node, collecting only the values that actually appear (this requires reading all queries in advance — an “offline processing” approach).

Algorithm

1. Flatten the tree into an array using Euler Tour

Compute \(tin[v]\) and \(tout[v]\) using iterative DFS (recursive DFS is avoided since the depth can reach \(10^5\)).

• Upon visiting: timer += 1, tin[v] = timer
• After finishing the subtree exploration: tout[v] = timer

The interval corresponding to subordinates is then: - \(L = tin[v] + 1\) - \(R = tout[v]\)

2. Rewrite “\(>T\)” as “\(\le T\)”

Let total = R-L+1 be the number of elements in the interval. Then:

• Count of \(>T\) = total - (count of <=T)

So what we need is “the count of elements \(\le T\) in the interval.”

3. 2D BIT (position × value)

Outer: BIT over positions (Euler Tour indices)

• add(pos, val, delta): increase/decrease the count of value val at position pos by delta (updates use pairs of +1 and -1)
• sum_prefix(pos, val): count of values \(\le val\) among positions \(1..pos\)

The count of “\(\le T\)” in interval \([L,R]\) is: - sum_prefix(R, T) - sum_prefix(L-1, T)

Inner: Each outer BIT node holds a “BIT over values”

Each outer BIT node k is responsible for a certain set of positions (an interval determined by BIT’s structure). We collect all values that can appear at the positions this node is responsible for, sort and deduplicate them, and build a coordinate-compressed BIT (array) from them.

4. Pre-collecting values to enable coordinate compression

Since future values from updates are also needed, we do the following:

• For each position tin[v], collect:
  • The initial value A[v]
  • All values x that this employee’s salary may be updated to

Then, when constructing the outer BIT: - Distribute the candidate value list for position p to all BIT propagation targets k = p, p+(p&-p), ... (In the code: coords[k].extend(vals))

This way, each coords[k] becomes “the set of values that can appear at this node,” allowing the inner BIT to be constructed.

5. Query processing

• Query 1 1 v x:
  • At position p = tin[v], reflect the “old salary” with -1 and the new salary with +1
• Query 2 2 v:
  • \(L=tin[v]+1,\ R=tout[v]\)
  • If there are no subordinates (\(L>R\)), output 0
  • Otherwise:
    • le = count of <= A[v] in [L,R]
    • ans = (R-L+1) - le

Complexity

• Time complexity: \(O\big((N+Q)\log^2 N\big)\)
  • Because both updates and prefix sum computations take \(O(\log N)\) for the outer BIT and \(O(\log N)\) for the inner BIT
• Space complexity: \(O\big((N+Q)\log N\big)\)
  • Because each update value is distributed to multiple outer BIT nodes (typically \(\log N\) times)

Implementation notes

• Subordinates do not include the employee themselves, so be sure to use the interval \([tin[v]+1, tout[v]]\) (this is a common source of bugs).

• In Python, recursive DFS is dangerous, so use iterative DFS with a stack as shown in the code.

• Since the 2D BIT tends to be memory-heavy, the code:

  • Stores inner BITs using array('i') (equivalent to C arrays)

  • Sorts coords[k] and deduplicates in-place to save memory.

    Source Code

import sys
from bisect import bisect_left, bisect_right
from array import array

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)

    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = next(it)

    children = [[] for _ in range(N + 1)]
    if N >= 2:
        for v in range(2, N + 1):
            p = next(it)
            children[p].append(v)

    tin = [0] * (N + 1)
    tout = [0] * (N + 1)
    timer = 0
    stack = [(1, 0)]
    while stack:
        v, st = stack.pop()
        if st == 0:
            timer += 1
            tin[v] = timer
            stack.append((v, 1))
            ch = children[v]
            for c in reversed(ch):
                stack.append((c, 0))
        else:
            tout[v] = timer

    queries = []
    pos_vals = [[] for _ in range(N + 1)]  # by Euler position
    for v in range(1, N + 1):
        pos_vals[tin[v]].append(A[v])

    for _ in range(Q):
        t = next(it)
        if t == 1:
            v = next(it)
            x = next(it)
            queries.append((1, v, x))
            pos_vals[tin[v]].append(x)
        else:
            v = next(it)
            queries.append((2, v))

    coords = [[] for _ in range(N + 1)]
    for p in range(1, N + 1):
        vals = pos_vals[p]
        if len(vals) > 1:
            vals = list(set(vals))
            vals.sort()
        k = p
        while k <= N:
            coords[k].extend(vals)
            k += k & -k

    bits = [None] * (N + 1)
    for k in range(1, N + 1):
        arr = coords[k]
        arr.sort()
        m = 1
        for i in range(1, len(arr)):
            if arr[i] != arr[m - 1]:
                arr[m] = arr[i]
                m += 1
        del arr[m:]
        bits[k] = array('i', [0]) * (len(arr) + 1)

    def add(pos, val, delta):
        k = pos
        while k <= N:
            ck = coords[k]
            idx = bisect_left(ck, val) + 1
            bk = bits[k]
            j = idx
            blen = len(bk)
            while j < blen:
                bk[j] += delta
                j += j & -j
            k += k & -k

    def sum_prefix(pos, val):
        res = 0
        k = pos
        while k > 0:
            ck = coords[k]
            idx = bisect_right(ck, val)
            bk = bits[k]
            j = idx
            while j > 0:
                res += bk[j]
                j -= j & -j
            k -= k & -k
        return res

    for v in range(1, N + 1):
        add(tin[v], A[v], 1)

    out_lines = []
    for q in queries:
        if q[0] == 1:
            _, v, x = q
            old = A[v]
            if old != x:
                p = tin[v]
                add(p, old, -1)
                add(p, x, 1)
                A[v] = x
        else:
            _, v = q
            l = tin[v] + 1
            r = tout[v]
            if l > r:
                out_lines.append("0")
                continue
            th = A[v]
            total = r - l + 1
            le = sum_prefix(r, th) - sum_prefix(l - 1, th)
            out_lines.append(str(total - le))

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.