Problem 13: Heavy-Light Decomposition
Problem Statement: Perform Heavy-Light Decomposition (HLD) on a tree to answer path queries efficiently.
Input
First line contains n and q. Next n-1 lines contain the edges of the tree. Then q queries follow: each query gives two nodes u and v.
Output
For each query, print the sum of values on the path between u and v (assume all nodes have an initial value of 1).
Examples
Input:
5 2
1 2
1 3
2 4
2 5
4 5
3 4
Output:
3
4
Solution Explanation
Method 1: Decompose the tree by selecting heavy and light edges and build a segment tree on the heavy path indices, then answer each query by climbing the tree in O(log n) time. Method 2: Use a simpler DFS-based approach for smaller trees although it will not be as efficient for many queries.
Solution in C++
// Due to complexity, this is a simplified outline.
#include
using namespace std;
const int N = 100005;
vector adj[N];
int parent[N], depth[N], heavy[N], head[N], pos[N], curPos;
int seg[4*N];
int dfs(int u, int p){
parent[u]=p; depth[u] = (p==-1?0:depth[p]+1);
int size=1, maxSize=0;
heavy[u] = -1;
for (int v: adj[u]){
if(v==p) continue;
int subSize = dfs(v, u);
if(subSize > maxSize) { maxSize = subSize; heavy[u] = v; }
size += subSize;
}
return size;
}
void decompose(int u, int h){
head[u] = h; pos[u] = curPos++;
if(heavy[u]!=-1) decompose(heavy[u], h);
for(int v: adj[u]){
if(v==parent[u] || v==heavy[u]) continue;
decompose(v, v);
}
}
// Dummy segment tree functions
void buildSeg(int idx, int l, int r){
if(l==r){ seg[idx]=1; return; }
int mid = (l+r)/2;
buildSeg(2*idx, l, mid);
buildSeg(2*idx+1, mid+1, r);
seg[idx]= seg[2*idx] + seg[2*idx+1];
}
int querySeg(int idx, int l, int r, int ql, int qr){
if(ql>r || qr depth[head[v]]) swap(u,v);
res += querySeg(1, 0, n-1, pos[head[v]], pos[v]);
v = parent[head[v]];
}
if(depth[u] > depth[v]) swap(u,v);
res += querySeg(1, 0, n-1, pos[u], pos[v]);
return res;
}
int main(){
int n, q; cin >> n >> q;
for(int i=1;i<=n;i++) { adj[i].clear(); }
for(int i=1;i> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
curPos=0;
dfs(1,-1);
decompose(1,1);
buildSeg(1, 0, n-1);
while(q--){
int u,v; cin >> u >> v;
cout << queryPath(u,v,n) << "
";
}
return 0;
}