UAIC Competitive Programming

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\n1 2\n1 3\n2 4\n2 5\n4 5\n3 4

Output:
3\n4

Solution in C++


// Due to complexity, this is a simplified outline.
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> 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<l)return 0;
    if(ql<=l && r<=qr)return seg[idx];
    int mid = (l+r)/2;
    return querySeg(2*idx, l, mid, ql, qr) + querySeg(2*idx+1, mid+1, r, ql, qr);
}

int queryPath(int u, int v, int n){
    int res=0;
    while(head[u]!=head[v]){
        if(depth[head[u]] > 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<n;i++){
        int u,v; cin >> 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) << "\n";
    }
    return 0;
}