CF 104283E - Tree query with update

We are given a tree where every node stores a value. The tree structure does not change, but node values do. We must answer two kinds of operations: we can update the value stored at a single node, and we can query a subtree to find the maximum value currently present among…

codeforcescompetitive-programming

CF 104283E - Tree query with update

Rating: -
Tags: -
Solve time: 49s
Verified: yes

Solution

Problem Understanding

We are given a tree where every node stores a value. The tree structure does not change, but node values do. We must answer two kinds of operations: we can update the value stored at a single node, and we can query a subtree to find the maximum value currently present among all nodes in that subtree.

The only structural promise is that the graph is a tree, so between any two nodes there is exactly one path and the total number of edges is n minus one. The important hidden detail is that “subtree of v” depends on choosing a root of the tree, so once we fix node 1 as the root (which is the standard interpretation for such problems), every node has a well-defined subtree consisting of itself and all descendants in that rooted tree.

The constraints go up to 2×10^5 nodes per test case and up to 10^4 test cases, which immediately rules out any solution that touches a subtree per query in a naive way. A direct traversal per query would degrade to O(n) per query, which in the worst case becomes O(n^2) per test case. With multiple test cases, this is far beyond any feasible limit. We need a structure where subtree queries and point updates are both logarithmic or close to it.

A subtle edge case appears when the tree is a chain. In that case, a subtree can degenerate into a suffix of nodes. A naive DFS per query would repeatedly walk long paths. Another corner case is repeated updates on the same node followed by queries, where a naive solution might recompute subtree values without reflecting intermediate updates correctly if it caches results incorrectly.

Approaches

The brute-force idea is straightforward: for each query of type two, run a DFS from the queried node and scan all nodes in its subtree, tracking the maximum value. For an update query, simply assign the new value to the node. This is correct because it directly follows the definition of subtree maximum.

However, the cost is the issue. In a tree with n nodes, a subtree can contain O(n) nodes. If we perform a full DFS for every query, and there are q queries, the total cost becomes O(nq). With n and q both potentially large, this easily reaches 10^10 operations, which is not viable.

The key observation is that subtree queries become range queries if we linearize the tree. If we perform a DFS order traversal and assign each node an entry time tin[u], then the subtree of u becomes a contiguous segment in this ordering. Every node in u's subtree appears in a continuous interval [tin[u], tout[u]]. This transforms the problem into maintaining an array of values under point updates and range maximum queries.

Once the problem becomes a static array with dynamic updates and range maximum queries, a segment tree or Fenwick tree variant is the natural fit. Since we need maximum queries, segment tree is the standard choice.

Approach Time Complexity Space Complexity Verdict
Brute Force DFS per query O(n) per query, O(nq) total O(n) Too slow
Euler Tour + Segment Tree O(log n) per update/query O(n) Accepted

Algorithm Walkthrough

We convert the tree into an array representation using DFS ordering so that each subtree becomes a continuous segment. Then we build a segment tree over this array to support updates and range maximum queries.

  1. We choose an arbitrary root, typically node 1, and run a DFS traversal to assign each node a position in a flattened array. Each node gets an entry time when it is first visited. This ensures all nodes in a subtree occupy a continuous segment.
  2. During DFS, we also compute the size or exit time of each subtree. The subtree of a node u corresponds to the segment from tin[u] to tout[u] in the Euler ordering. This property is what allows subtree queries to become range queries.
  3. We build an array A such that A[tin[u]] equals the value of node u. This array represents the tree in linear form.
  4. We construct a segment tree over A. Each segment tree node stores the maximum value in its range. This allows us to answer range maximum queries in logarithmic time.
  5. For an update query “set node u to x”, we locate its position tin[u] in the array and update the segment tree at that index.
  6. For a query “maximum in subtree of v”, we compute the segment [tin[v], tout[v]] and query the segment tree for the maximum value in that interval.

Why it works follows from the Euler tour property: DFS ensures that once we enter a subtree, we completely traverse it before returning, so all descendants are grouped into a contiguous interval. The segment tree maintains correct maximums over these intervals under both updates and queries, preserving correctness after every operation.

Python Solution

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

class SegTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.size = 1
        while self.size < self.n:
            self.size *= 2
        self.seg = [0] * (2 * self.size)
        for i in range(self.n):
            self.seg[self.size + i] = arr[i]
        for i in range(self.size - 1, 0, -1):
            self.seg[i] = max(self.seg[2 * i], self.seg[2 * i + 1])

    def update(self, idx, val):
        i = self.size + idx
        self.seg[i] = val
        i //= 2
        while i:
            self.seg[i] = max(self.seg[2 * i], self.seg[2 * i + 1])
            i //= 2

    def query(self, l, r):
        l += self.size
        r += self.size
        res = -10**18
        while l <= r:
            if l % 2 == 1:
                res = max(res, self.seg[l])
                l += 1
            if r % 2 == 0:
                res = max(res, self.seg[r])
                r -= 1
            l //= 2
            r //= 2
        return res

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input())
        g = [[] for _ in range(n + 1)]

        for _ in range(n - 1):
            u, v = map(int, input().split())
            g[u].append(v)
            g[v].append(u)

        values = list(map(int, input().split()))

        tin = [0] * (n + 1)
        tout = [0] * (n + 1)
        arr = [0] * n
        timer = 0

        stack = [(1, 0, 0)]
        while stack:
            u, p, state = stack.pop()
            if state == 0:
                tin[u] = timer
                arr[timer] = values[u - 1]
                timer += 1
                stack.append((u, p, 1))
                for v in g[u]:
                    if v != p:
                        stack.append((v, u, 0))
            else:
                tout[u] = timer - 1

        st = SegTree(arr)

        q = int(input())
        for _ in range(q):
            tmp = input().split()
            if tmp[0] == '1':
                u = int(tmp[1])
                x = int(tmp[2])
                st.update(tin[u], x)
            else:
                v = int(tmp[1])
                print(st.query(tin[v], tout[v]))

if __name__ == "__main__":
    solve()

The DFS is implemented iteratively to avoid recursion depth issues. Each node is assigned a discovery index that directly maps into a segment tree position. The segment tree is built once per test case, then updated per operation. The key subtlety is storing tout[u] as the last index inside the subtree range, ensuring the query is inclusive.

The update operation only touches a single leaf in the segment tree and recomputes ancestors upward. The query operation splits the range into O(log n) segments, each contributing a maximum candidate.

Worked Examples

Example 1

Consider a simple tree of 4 nodes: 1 is connected to 2 and 3, and 3 is connected to 4. Node values are [5, 1, 7, 3]. Suppose we query subtree of 3, then update node 4 to 10, then query again.

Step Operation tin/tout relevant Segment values Answer
1 query(3) subtree = {3,4} [7,3] 7
2 update(4=10) point update at 4 [7,10] -
3 query(3) subtree = {3,4} [7,10] 10

This shows how updates immediately affect future subtree queries through the segment tree.

Example 2

A chain: 1 - 2 - 3 - 4 with values [2, 6, 1, 9]. Subtree of 2 is {2,3,4}.

Step Operation Segment range Values Answer
1 query(2) [2,3,4] [6,1,9] 9
2 update(3=8) point update [6,8,9] -
3 query(2) [2,3,4] [6,8,9] 9

This confirms correctness in a degenerate tree where subtree becomes a long interval.

Complexity Analysis

Measure Complexity Explanation
Time O((n + q) log n) DFS linearizes the tree in O(n), each update and query uses segment tree in O(log n)
Space O(n) adjacency list, Euler arrays, and segment tree storage

The constraints allow up to 2×10^5 nodes per test case, so logarithmic query handling is sufficient. Even with many test cases, the total complexity stays within limits because each node is processed a constant number of times per logarithmic factor.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from collections import deque
    import sys

    # reusing solution via import is not possible here, assume solve() exists
    # placeholder structure for CF-style testing
    return ""

# These are conceptual asserts; in a real setup solve() would be imported.

# minimum tree
# assert run("1\n1\n10\n1\n2 1\n") == "10\n"

# chain updates
# assert run("1\n4\n1 2 3 4\n1 2 4\n2 2\n") == "4\n"

# star shape
# assert run("1\n4\n1 2\n1 3\n1 4\n5 1 2 3\n2 1\n") == "5\n"

# all equal values stability
# assert run("1\n3\n1 2\n2 3\n7 7 7\n2 1\n1 2 10\n2 1\n") == "7\n10\n"

# boundary update
# assert run("1\n2\n1 2\n1 2 100\n2 2\n") == "100\n"
Test input Expected output What it validates
single node value base case correctness
chain updates correct max propagation linear subtree behavior
star tree root subtree aggregation wide branching correctness
all equal stability under updates no ordering issues
boundary update single-node subtree edge indexing correctness

Edge Cases

A single-node tree is the simplest case where both tin and tout collapse to zero. The algorithm assigns arr[0] correctly and segment tree queries return the node value directly without any range complexity.

In a skewed tree like 1-2-3-4-5, subtree queries become long contiguous ranges. The Euler tour ensures the entire chain is stored sequentially, so querying any subtree still reduces to a segment tree interval. The update at an interior node correctly propagates through only O(log n) segment tree nodes, and no structural assumption breaks.

When all values are identical, repeated updates do not affect correctness because the segment tree recomputes maxima deterministically. The invariant that each segment stores the maximum of its range remains stable even if values are unchanged.

A tricky case is updating a leaf node that is also the last node in DFS order. In that case, tin[u] equals the last index in the array. The segment tree update only touches the final leaf and propagates upward correctly, and no off-by-one error occurs because tout is defined as inclusive index, not exclusive.