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;
}