Model answer
The task
The title and tags suggest finding distances between nodes in a weighted tree, potentially while edge weights change. The exact query and update requirements are unclear, so the solution below covers the common dynamic version: update an edge weight and query the path distance between two nodes.
Key idea
A tree path distance is root_distance[u] + root_distance[v] - 2 * root_distance[lca(u, v)]. Changing an edge affects the root distance of every node in the child endpoint’s subtree, so a Fenwick tree can apply that change to a subtree and retrieve each node’s current root distance.
Approach
- Root the tree at node
0; record parent, depth, initial root distance, and Euler-tour subtree intervals. - Build a binary-lifting table to find lowest common ancestors.
- Store each edge’s child endpoint, so an edge update becomes a range addition over that child’s subtree.
- Use a Fenwick tree for subtree range additions and point queries.
- Compute a distance query with the LCA formula and the current root distances.
class Fenwick:
"""Supports range additions and point queries over [0, n)."""
def __init__(self, n):
self.n = n
self.bit = [0] * (n + 1)
def _add(self, index, delta):
i = index + 1
while i <= self.n:
self.bit[i] += delta
i += i & -i
def range_add(self, left, right, delta):
"""Add delta to every position in [left, right)."""
self._add(left, delta)
if right < self.n:
self._add(right, -delta)
def point_query(self, index):
total = 0
i = index + 1
while i:
total += self.bit[i]
i -= i & -i
return total
class WeightedTreeDistance:
def __init__(self, n, edges):
"""
edges contains (u, v, weight) triples.
Nodes are numbered 0 through n - 1.
"""
self.n = n
self.edges = [list(edge) for edge in edges]
graph = [[] for _ in range(n)]
for edge_id, (u, v, weight) in enumerate(self.edges):
graph[u].append((v, edge_id))
graph[v].append((u, edge_id))
self.parent = [0] * n
self.depth = [0] * n
self.base_distance = [0] * n
self.tin = [0] * n
self.tout = [0] * n
self.edge_child = [-1] * len(edges)
# Enter/exit events produce contiguous Euler-tour subtree intervals.
clock = 0
stack = [(0, 0, -1, 0, False)]
while stack:
node, parent, edge_id, distance, exiting = stack.pop()
if exiting:
self.tout[node] = clock
continue
self.parent[node] = parent
self.depth[node] = 0 if node == parent else self.depth[parent] + 1
self.base_distance[node] = distance
self.tin[node] = clock
clock += 1
stack.append((node, parent, edge_id, distance, True))
for neighbor, next_edge in reversed(graph[node]):
if neighbor == parent:
continue
self.edge_child[next_edge] = neighbor
next_distance = distance + self.edges[next_edge][2]
stack.append((neighbor, node, next_edge, next_distance, False))
levels = max(1, n.bit_length())
self.up = [self.parent[:]]
for _ in range(1, levels):
previous = self.up[-1]
self.up.append([previous[previous[node]] for node in range(n)])
self.changes = Fenwick(n)
def _lca(self, a, b):
if self.depth[a] < self.depth[b]:
a, b = b, a
difference = self.depth[a] - self.depth[b]
bit = 0
while difference:
if difference & 1:
a = self.up[bit][a]
difference >>= 1
bit += 1
if a == b:
return a
for level in range(len(self.up) - 1, -1, -1):
if self.up[level][a] != self.up[level][b]:
a = self.up[level][a]
b = self.up[level][b]
return self.parent[a]
def update_edge(self, edge_id, new_weight):
u, v, old_weight = self.edges[edge_id]
child = self.edge_child[edge_id]
delta = new_weight - old_weight
self.edges[edge_id][2] = new_weight
self.changes.range_add(self.tin[child], self.tout[child], delta)
def distance(self, u, v):
ancestor = self._lca(u, v)
def root_distance(node):
return self.base_distance[node] + self.changes.point_query(self.tin[node])
return root_distance(u) + root_distance(v) - 2 * root_distance(ancestor)
Complexity:
- Time:
O(n log n) preprocessing; O(log n) per update or distance query. - Space:
O(n log n) for the ancestor table and tree data.
Common follow-ups
- What if edge weights never change? Use the initial root distances and LCA formula; no Fenwick tree is needed.
- What if the tree has negative edge weights? The same path-sum method works; a tree has a unique path.
- What if queries ask for the actual path, not just its distance? Find the LCA, then collect each endpoint’s ancestors and join the two path portions.