You are given a tree consisting of n nodes. The nodes are numbered 1,2,...,n. Each node has a value. Your task is to process following types of queries:
Solution: We will use Heavy-Light Decomposition (HLD) - a technique used to efficiently handle queries (such as max, xor, sum, …) on the path between any two nodes in a tree. A naive solution requires traversing the entire path, which can take O(n) in the worst case. Heavy-Light Decomposition (HLD) provides a way to reduce this to O(log² n) per query.
Prerequisite knowledge:
How it works?
Why choose the largest child?
Suppose a node u has a subtree of size sz[u].
This ensures:
đź’ˇ In other words:
Build chains:
Consecutive heavy edges are connected to form a chain, and each chain is compressed into a continuous segment of an array (using Euler Tour + position numbering pos[] ) to reduce time complexity.
→ Then, instead of querying directly on the tree, we only need to query over contiguous array ranges.
Initialization and Input
#include <iostream>
#include <vector>
#define pp push_back
using namespace std;
using ll = long long;
const char el ='\n';
const char sp = ' ';
const int maxn = 2e5+5;
int n,q;
int sz[maxn],h[maxn],par[maxn],head[maxn],id[maxn],pos[maxn],a[maxn];
// sz[u] = size of subtree rooted at u
// h[u] = depth of u
// par[u] = parent of u
// head[c] = head node of chain c
// id[u] = which chain node u belongs to
// pos[u] = position of u in the segment tree
// a[u] = initial value of node u
int curchain,curpos; // track current chain index and position
vector<int> adj[maxn];
int st[4*maxn]; // segment tree
void input()
{
cin>>n>>q;
for(int i=1;i<=n;++i) cin>>a[i]; // initial values
for(int i=1,u,v;i<n;++i)
{
cin>>u>>v;
adj[u].pp(v);
adj[v].pp(u);
}
DFS(1,0); // prepare size, depth, parent
curpos=curchain=1;
HLD(1,0); // build decomposition
for(int i=1,t,u,v;i<=q;++i)
{
cin>>t>>u>>v;
if(t==1) udt(1,1,n,pos[u],v); // point update on node u
else cout<<solve(u,v)<<sp; // query max on path u→v
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
input();
return 0;
}
-----------------------------------------------------------------
Depth-first search: to pre-compute subtree sizes (to pick heavy child), depths, and parents.
void DFS(int u, int v)
{
h[u]=h[v]+1; // depth[u] = depth[parent]+1
sz[u]=1;
par[u]=v;
for(int i:adj[u])
{
if(i==v) continue;
DFS(i,u);
sz[u]+=sz[i]; // accumulate size
}
}
-----------------------------------------------------------------
Segment Tree: for point update + range maximum query
void udt(int id, int l, int r, int u, int v)
{
if(l>u or r<u) return; // outside the update position
if(l==r) st[id]=v; // leaf node, assign value
else
{
int mid=(l+r)/2;
udt(id*2,l,mid,u,v);
udt(id*2+1,mid+1,r,u,v);
st[id]=max(st[id*2],st[id*2+1]); // recalc parent node
}
}
int gt(int id, int l, int r, int u, int v)
{
if(l>v or r<u) return 0; // outside range
if(l>=u && r<=v) return st[id]; // fully inside range
else
{
int mid=(l+r)/2;
return max(gt(id*2,l,mid,u,v), gt(id*2+1,mid+1,r,u,v));
}
}
-----------------------------------------------------------------
Heavy-Light Decomposition: to build chains and map nodes to segment tree positions.
👉 Key idea:
void HLD(int u, int v)
{
if(head[curchain]==0) head[curchain]=u; // new chain → assign head
id[u]=curchain; // mark chain of u
pos[u]=curpos; // position in segtree
udt(1,1,n,curpos,a[u]); // insert value into segtree
++curpos;
int tmp=0; // tmp = heavy child
for(int i:adj[u])
{
if(i==v) continue;
if(sz[tmp]<sz[i]) tmp=i; // pick child with largest subtree
}
if(tmp!=0) HLD(tmp,u); // continue heavy edge in same chain
for(int i:adj[u]) // process light edges
{
if(i!=v && i!=tmp)
{
++curchain; // new chain
HLD(i,u); // decompose light child
}
}
}
-----------------------------------------------------------------
Query on path u → v: find maximum value on path u → v
int solve(int u, int v)
{
int ans=0;
while(id[u]!=id[v]) // while not in the same chain
{
if(id[u]<id[v]) swap(u,v);
// query from head of u’s chain to u
ans=max(ans, gt(1,1,n,pos[head[id[u]]], pos[u]));
u=par[head[id[u]]]; // move u up to parent of its chain head
}
if(h[u]>h[v]) swap(u,v); // now same chain → query directly
ans=max(ans, gt(1,1,n,pos[u],pos[v]));
return ans;
}