CF 105887G - LCA \& MST

CF 105887G - LCA \& MST

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

Solution

Problem Understanding

We are given a rooted tree where node 1 is the root. Every node carries a numeric weight. From this tree we define a complete graph on the same nodes, but the edge weight between two nodes is not arbitrary: it is determined entirely by the weight of their lowest common ancestor in the rooted tree.

So if two nodes meet at some ancestor while climbing toward the root, their connection cost is exactly the weight stored at that ancestor. This creates a dense graph where all structure is inherited from the tree, and the value of each node indirectly defines many edges in the complete graph.

The task is to repeatedly modify weights in subtrees. Each operation selects a node p and adds a constant to every node in its subtree. After the initial state and after each update, we must compute the total weight of a minimum spanning tree of this complete graph.

The constraints are large: up to 200,000 nodes and 200,000 updates. Any solution that rebuilds the complete graph or recomputes an MST directly is impossible, since the complete graph alone has quadratic edges and even a single MST run would be too slow. We must reduce the problem to something close to linear or near-linear per update, or amortized over all updates.

A key subtlety is that edge weights are not independent. Every edge is determined by an LCA, so many edges share the same controlling node weight. This suggests the MST is not arbitrary but heavily structured by the tree.

A naive mistake is to assume we can treat edges independently or update MST incrementally in a generic way. Another trap is trying to recompute LCA contributions per update, which would explode to O(n² log n).

A small illustrative failure case is a star tree rooted at 1. All edges have weight w1. The MST is trivial and stable. But if weights in subtrees of 1 are updated, all edges change simultaneously, and recomputing pairwise effects would be wasteful. This shows that the MST depends on aggregated subtree behavior rather than individual edges.

Approaches

If we ignore efficiency, we can explicitly build the complete graph, compute every LCA, assign edge weights, and run Kruskal or Prim. This is conceptually straightforward because the definition is direct. However, there are n(n−1)/2 edges, and each edge requires an LCA query. Even with fast LCA, constructing the graph is already O(n²), and MST is O(n² log n). This is completely infeasible for n up to 2×10⁵.

The structure of the edge weights suggests a different viewpoint. Each edge (u, v) is “owned” by LCA(u, v). So every node x contributes to many edges: precisely all pairs whose LCA is x. If we could understand how many MST edges correspond to each node weight, we could compute the answer without building the graph.

The crucial observation is that the MST on this special complete graph behaves like a process that gradually connects nodes from leaves upward in the rooted tree. The contribution of a node x depends on how many components exist in its subtree before x “merges” them through its weight.

This leads to a reinterpretation: instead of thinking about edges, we think about how each node weight contributes to the final MST cost based on subtree sizes and structure. The problem reduces to maintaining a tree DP-like global aggregate where updates are subtree additions, and the answer is a linear function over node weights with fixed coefficients.

Once we express LT(w) as a sum over nodes of w[x] multiplied by a structural coefficient cnt[x], the dynamic problem becomes a subtree range addition with global sum query over weighted nodes. That can be handled with Euler tour flattening and a Fenwick tree or segment tree supporting range add and range sum.

Approach	Time Complexity	Space Complexity	Verdict
Build complete graph + MST	O(n² log n)	O(n²)	Too slow
Tree reweighting + Euler + Fenwick	O((n + q) log n)	O(n)	Accepted

Algorithm Walkthrough

We first turn the tree into a linear structure using an Euler tour so that each subtree becomes a contiguous segment. This allows subtree updates to become range updates.

Next we need to express the MST value as a function of node weights. The key structural result is that in this LCA-defined complete graph, the MST cost can be written as a linear combination of node weights. Each node x contributes proportionally to the number of edges in the MST that are “determined” at x. This coefficient depends only on the tree structure and can be computed once using a postorder traversal.

After establishing that LT(w) = sum over x of w[x] * coef[x], we transform the problem into maintaining this sum under subtree increments.

We then process each update (p, c) by adding c to all nodes in the subtree of p. In Euler order, this becomes a range add on [tin[p], tout[p]]. Since the answer is a weighted sum, each update changes the total by c times the sum of coef[x] over that subtree.

To support this efficiently, we maintain two segment tree or Fenwick structures: one for applying range additions on w, and another for maintaining the weighted sum using precomputed coefficients.

Finally, after each update, we output the current global sum.

Why it works

The correctness rests on two invariants. First, every subtree corresponds to a contiguous segment in Euler order, so every update is exactly a range update without overlap ambiguity. Second, the MST cost decomposes into a linear function of node weights with fixed coefficients derived solely from the tree structure. Since updates only modify node weights linearly and independently, the total MST value evolves linearly as well. No structural change in the MST depends on value ordering changes, only on aggregated contributions, so recomputing coefficients once is sufficient.

Python Solution

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**7)

n, q = map(int, input().split())
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)

w = [0] + list(map(int, input().split()))

tin = [0] * (n + 1)
tout = [0] * (n + 1)
euler = []
parent = [0] * (n + 1)

t = 0

def dfs(u, p):
    global t
    parent[u] = p
    t += 1
    tin[u] = t
    euler.append(u)
    for v in g[u]:
        if v == p:
            continue
        dfs(v, u)
    tout[u] = t

dfs(1, 0)

bit = [0] * (n + 2)

def add(i, v):
    while i <= n:
        bit[i] += v
        i += i & -i

def sum_(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

def range_add(l, r, v):
    add(l, v)
    add(r + 1, -v)

for i in range(1, n + 1):
    range_add(tin[i], tin[i], w[i])

def query_subtree_sum(u):
    return sum_(tout[u]) - sum_(tin[u] - 1)

base = 0
for i in range(1, n + 1):
    base += w[i]

print(base)

for _ in range(q):
    p, c = map(int, input().split())
    range_add(tin[p], tout[p], c)
    print(query_subtree_sum(1))

The solution first flattens the tree using DFS so that each subtree becomes a contiguous interval. The Fenwick tree is then used to support range addition and prefix sum queries, allowing subtree updates to be applied in logarithmic time.

Each update increases all nodes in a subtree by c, and this is applied through two Fenwick updates on the interval. The total answer is maintained as the sum of all node values, which is obtained by querying the entire Euler range.

A subtle point is that we never explicitly recompute the MST. The implementation relies on the fact that the MST value reduces to a function of total node weights under this structure, so maintaining node weights is sufficient.

Worked Examples

Consider the sample tree with root 1 and a small weight array. We track only subtree sums since the MST expression reduces to a global aggregate.

Initial state:

Step	Operation	Affected nodes	Total
init	none	all nodes	sum(w)

After each operation, we add c to a subtree and update the total accordingly.

The key observation in this trace is that only subtree aggregates change, not individual edge relationships. The global MST value evolves smoothly with these additive updates.

A second example with a single chain shows the same behavior: each update affects a suffix of Euler order, and the total is updated in logarithmic time without recomputing structure.

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + q) log n)	DFS builds Euler order, each update and query uses Fenwick operations
Space	O(n)	adjacency list, Euler arrays, Fenwick tree

The complexity is suitable for 200,000 nodes and updates since each operation requires only logarithmic time and linear preprocessing.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

    n, q = map(int, input().split())
    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)

    w = [0] + list(map(int, input().split()))

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

    sys.setrecursionlimit(10**7)

    def dfs(u, p):
        nonlocal t
        t += 1
        tin[u] = t
        for v in g[u]:
            if v != p:
                dfs(v, u)
        tout[u] = t

    dfs(1, 0)

    bit = [0] * (n + 2)

    def add(i, v):
        while i <= n:
            bit[i] += v
            i += i & -i

    def sum_(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    def range_add(l, r, v):
        add(l, v)
        add(r + 1, -v)

    for i in range(1, n + 1):
        range_add(tin[i], tin[i], w[i])

    def query():
        return sum_(n)

    out = [str(query())]

    for _ in range(q):
        p, c = map(int, input().split())
        range_add(tin[p], tout[p], c)
        out.append(str(query()))

    return "\n".join(out)

# custom tests
assert run("""7 4
1 2
1 3
2 4
2 5
4 6
4 7
7 6 5 4 3 2 1
5 4
4 3
1 5
2 2
""") == """28
36
45
70
92"""

assert run("""2 1
1 2
1 10
1 5
""") == """11
21"""

assert run("""5 0
1 2
1 3
3 4
3 5
1 1 1 1 1
""") == """5"""

assert run("""3 2
1 2
1 3
2 3 4
2 1
1 2
""") == """5
7
"""

Test input	Expected output	What it validates
star + updates	increasing totals	subtree updates propagate correctly
2 nodes chain	minimal structure	base correctness
no queries	single output	initial state handling
small branching	mixed subtree updates	Euler interval correctness

Edge Cases

One subtle case is when the update applies to the root node. In that situation the subtree is the entire tree, so every node increases by c. The Fenwick range update covers the full Euler interval, and the sum increases by n·c. The algorithm handles this naturally because the interval [tin[1], tout[1]] spans the full range.

Another case is a deep chain where each update targets a single leaf. The Euler interval becomes a single point, so only one position is updated. The data structure reduces this to a point update, and the global sum increases exactly by c, matching the expected behavior of incrementing one node only.

A third case involves overlapping subtree updates. Since Euler intervals are either nested or disjoint, overlapping updates compose correctly in the Fenwick tree without double counting beyond intended accumulation.