https://www.spoj.com/problems/GRASSPLA/

C++ 14 clang 8.0

#include <cstdio>
#include <vector>
#include <fstream>
#include <iostream>
 
#define LSOne(S) (S & (-S))
 
using namespace std;
 
typedef pair <int,int> ii; 
 
const int NMAX = 100010;
const ii NNULL = make_pair(NMAX,NMAX);
 
int dfsNum, chainNum, chainPtr, sub_root, par[NMAX], level[NMAX], vec[NMAX], chainHeads[NMAX], chainId[NMAX], chainPos[NMAX], edges[NMAX], tree_size[NMAX];
vector<int> graph[NMAX];
ii tree[8*NMAX],coords[2*NMAX];
 
void dfs(int x,int p){
    vec[x] = ++dfsNum;
    coords[dfsNum] = make_pair(level[x],x);
    tree_size[x]++;
    for (int v : graph[x]){
        if (v == p) continue;
        par[v] = x;
        level[v] = level[x] + 1;
        dfs(v,x);
        tree_size[x] += tree_size[v];
        coords[++dfsNum] = make_pair(level[x],x);
    }
}
 
void HLD(int x,int p){
    if (!chainHeads[chainNum]) chainHeads[chainNum] = x;
 
    chainId[x] = chainNum;
    chainPos[x] = ++chainPtr;
    if (tree_size[x] == 1) return;
 
    int mx = 0, argmx = -1;
    for (int v : graph[x]){
        if (v == p) continue;
        if (tree_size[v] > mx){
            mx = tree_size[v];
            argmx = v;
        }
    }
 
    HLD(argmx,x);
    for (int v : graph[x]){
        if (v == p || v == argmx) continue;
        chainNum++;
        HLD(v,x);
    }
}
 
void update_ed(int pos,int val){
    while (pos < NMAX){
        edges[pos] += val;
        pos += LSOne(pos);
    }
}
 
int query_ed(int pos){
    int ans = 0;
    while (pos > 0){
        ans += edges[pos];
        pos -= LSOne(pos);
    }
    return ans;
}
 
void build_seg(int pos,int left,int right){
    if (left == right){
        tree[pos] = coords[left];
        return;
    }
    int mid = (left+right)/2;
    build_seg(2*pos,left,mid);
    build_seg(2*pos+1,mid+1,right);
    tree[pos] = min(tree[2*pos],tree[2*pos+1]);
}
 
ii query_seg(int pos,int left,int right,int i,int j){
    if (left > right || left > j || right < i) return NNULL;
    if (left >= i && right <= j){
        return tree[pos];
    }
    int mid = (left+right)/2;
    return min(query_seg(2*pos,left,mid,i,j),query_seg(2*pos+1,mid+1,right,i,j));
}
 
int LCA(int v1, int v2){
    return query_seg(1,1,dfsNum,min(vec[v1],vec[v2]),max(vec[v1],vec[v2])).second;
}
 
void query_up(int v1,int v2){
    int v1_ch,v2_ch;
    v2_ch = chainId[v2];
    while (true){
        v1_ch = chainId[v1];
        if (v1 == v2) break;
        if (v1_ch == v2_ch){
            update_ed(chainPos[v2]+1,1);
            update_ed(chainPos[v1]+1,-1);
            break;
        }
        update_ed(chainPos[chainHeads[v1_ch]],1);
        update_ed(chainPos[v1]+1,-1);
        v1 = chainHeads[v1_ch];
        v1 = par[v1];
    }
}
 
void doQuery(int u,int v){
    sub_root = LCA(u,v);
    query_up(u,sub_root);
    query_up(v,sub_root);
}
 
int main(){
    int N, M, i, v1, v2;
    ifstream input_file;
    input_file.open("input.txt");
    scanf("%d %d",&N,&M);
    // input_file >> N >> M;
    for (i=1; i<N; i++) {
 
        scanf("%d %d",&v1,&v2);
        // input_file >> v1 >> v2;
        graph[v1].push_back(v2);
        graph[v2].push_back(v1);
    }
 
    par[1] = 1;
    dfs(1,-1);
    build_seg(1,1,dfsNum);
    chainNum++;
    HLD(1,-1);
 
    for (i=0; i<M; ++i){
        char op;
        scanf(" %c",&op);
        // input_file >> op;
        // input_file >> v1 >> v2;
        scanf("%d %d",&v1,&v2);
        if (op == 'P') doQuery(v1,v2);
        else {
            if(level[v1] < level[v2]) swap(v1,v2);
            printf("%d\n",query_ed(chainPos[v1]));
        }
    }
    return 0;
}