Heavy Light Decomposition
We use the same tree, rooted at vertex . Each vertex stores a value . We support replacing one vertex value and finding the sum on a path, including both endpoints. The tree's edges stay fixed.
Vertices and array positions are numbered from . All intervals in this lesson include both endpoints.
The first pass prepares the information from the previous lesson:
The second pass assigns two new quantities: , the head of the chain containing , and , the position of in the array.
Use a heavy-first preorder:
The heavy child receives the next position immediately after its parent. No side branch is visited between them. Continuing this rule keeps the entire chain consecutive.
In the tree below, vertex is visited before at vertex , so is chosen as its heavy child.
Build one segment tree over , where . Its entries store vertex values in traversal order.
The traversal finishes every subtree before leaving it. Visiting the heavy child first changes the order of the children, but it preserves this DFS property.
Therefore, the subtree of occupies the interval .
The same segment tree can answer a subtree-sum query using this one interval.
Keeping chains consecutive is not sufficient. Arrange the vertices as :
Every chain is still consecutive. However, the subtree of now occupies positions . Vertices , which are outside that subtree, separate its two blocks.
DFS provides more than chain contiguity: it finishes an entire subtree before moving to a sibling's subtree. Our rearrangement breaks that rule.
Let and be the endpoints of the part of the path that we have not processed yet. Start the answer at .
While their chain heads differ:
The chosen portion starts at a chain head and ends at one current endpoint. Its positions are consecutive, so it needs one segment-tree query.
Jumping to the head's parent removes the entire processed portion, including the head itself. Each jump crosses one light edge.
The invariant is that the processed portions and the remaining path partition the original path: no vertex is missing or counted twice.
Write and , with and .
Suppose were an ancestor of . Both and would then lie on the root-to- path. Because is no deeper than , the path from to would contain .
But that entire path belongs to the chain headed by . This would put in 's chain, contradicting the fact that is the head of a different chain.
Thus is not an ancestor of . The lowest common ancestor of and lies strictly above , so the path from to contains the entire portion from up to .
After removing it, the remaining path connects the parent of to . The removed portion and the remaining path are disjoint, preserving the invariant. This reasoning also works when the two distinct heads have equal depths.
Choose and . Their depths are and , so the proposed rule chooses vertex .
However, . Processing its whole chain portion queries , containing vertices :
The requested path is . Vertex is outside it, while vertex has not been processed.
The correct comparison uses the heads: head has depth , while head has depth . Process vertex first, then jump to . The remaining vertices lie in one chain.
An endpoint's depth tells us where that endpoint lies. The head's depth tells us where the whole portion begins, which is the boundary we are about to remove.
When , the remaining path lies entirely inside one chain.
Within that chain, positions increase with depth. Put the shallower endpoint in and add the sum on .
This final interval includes the lowest common ancestor exactly once. A separate LCA computation is unnecessary. If the original endpoints are equal, the loop is skipped and this interval contains just that vertex.
For the query from to , the algorithm processes three portions:
First, head is deeper than head , so process and move from to . Next, head is deeper than head , so process and move from to .
The remaining endpoints are and , both in the root's chain. Process . The answer is .
Here, returns the sum on the inclusive interval :
Replacing with changes just one segment-tree position:
The heads, positions, and subtree sizes depend only on the tree's structure, so a value update does not change the decomposition.
Each chain-head jump crosses a light edge, so one path query uses intervals. Each segment-tree query takes time. Together, these give time per path query.
It does not work. To track the letters' order, write the corresponding vertex numbers:
The required order is . Our routine reads its intervals in increasing array order and processes them as , then , then .
There are two separate problems. The first and last portions are read in the opposite direction to the requested path. Also, the middle portion of the requested path, , is processed after the portion .
Sums and maxima are unchanged when we reorder their values. Concatenation depends on order. Supporting it requires preserving both the direction within each portion and the order in which portions are joined; changing the segment tree's operation alone is not enough.
In the previous lesson, we proved that any tree path consists of heavy-chain portions. We will now give those portions array positions and process them.
Suppose we keep each heavy chain consecutive, with its vertices in top-to-bottom order, but arrange the chain blocks however we like. Must every subtree still occupy one interval? Construct a counterexample using our tree, and explain what extra property the heavy-first DFS provides.
A student compares and instead of the depths of their heads, then processes the chosen endpoint's entire chain portion. Using our tree, find endpoints with different depths for which this rule includes a vertex outside the requested path. Explain why the deeper endpoint gives the wrong choice.
Suppose each vertex stores a letter, and a query must return the letters in order from the first endpoint to the second. Can we reuse exactly the same path routine by replacing addition with string concatenation? Use the query from to to justify your answer. Identify both where the direction inside a portion can change and where the order of the portions can change.
long long get_path(int v, int u) {
long long result = 0;
while (head[v] != head[u]) {
if (depth[head[v]] < depth[head[u]]) {
swap(v, u);
}
result += get(1, 1, n, pos[head[v]], pos[v]);
v = parent[head[v]];
}
if (depth[v] > depth[u]) {
swap(v, u);
}
result += get(1, 1, n, pos[v], pos[u]);
return result;
}
upd(1, 1, n, pos[v], x);
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 200200;
int n, q, tim;
int parent[N], depth[N], sz[N], heavy[N];
int head[N], pos[N];
long long a[N], base[N], t[4 * N];
vector<int> g[N];
void dfs_size(int v, int p) {
parent[v] = p;
sz[v] = 1;
for (int u : g[v]) {
if (u == p) {
continue;
}
depth[u] = depth[v] + 1;
dfs_size(u, v);
sz[v] += sz[u];
if (heavy[v] == 0 || sz[u] > sz[heavy[v]]) {
heavy[v] = u;
}
}
}
void decompose(int v, int h) {
head[v] = h;
pos[v] = ++tim;
base[tim] = a[v];
if (heavy[v] != 0) {
decompose(heavy[v], h);
}
for (int u : g[v]) {
if (u != parent[v] && u != heavy[v]) {
decompose(u, u);
}
}
}
void build(int x, int l, int r) {
if (l == r) {
t[x] = base[l];
return;
}
int m = (l + r) / 2;
build(x * 2, l, m);
build(x * 2 + 1, m + 1, r);
t[x] = t[x * 2] + t[x * 2 + 1];
}
void upd(int x, int l, int r, int p, long long y) {
if (l == r) {
t[x] = y;
return;
}
int m = (l + r) / 2;
if (p <= m) {
upd(x * 2, l, m, p, y);
} else {
upd(x * 2 + 1, m + 1, r, p, y);
}
t[x] = t[x * 2] + t[x * 2 + 1];
}
long long get(int x, int l, int r, int tl, int tr) {
if (tl > tr) {
return 0;
} else if (l == tl && r == tr) {
return t[x];
}
int m = (l + r) / 2;
return get(x * 2, l, m, tl, min(m, tr)) + get(x * 2 + 1, m + 1, r, max(m + 1, tl), tr);
}
long long get_path(int v, int u) {
long long result = 0;
while (head[v] != head[u]) {
if (depth[head[v]] < depth[head[u]]) {
swap(v, u);
}
result += get(1, 1, n, pos[head[v]], pos[v]);
v = parent[head[v]];
}
if (depth[v] > depth[u]) {
swap(v, u);
}
result += get(1, 1, n, pos[v], pos[u]);
return result;
}
void solve() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i < n; i++) {
int v, u;
cin >> v >> u;
g[v].push_back(u);
g[u].push_back(v);
}
dfs_size(1, 0);
decompose(1, 1);
build(1, 1, n);
while (q--) {
int type, v;
cin >> type >> v;
if (type == 1) {
long long x;
cin >> x;
upd(1, 1, n, pos[v], x);
} else {
int u;
cin >> u;
cout << get_path(v, u) << '\n';
}
}
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}