https://www.spoj.com/problems/COT/ I saw most mentioned that it could be solved using Persistent Segment Tree,HLD and also Centroid Decomposition. But I tried differently using parallel Binary Search + Fenwick tree.
I created two Fenwick trees of size 2 * n, one is for in values count and the other one is for out values count. While looping through all the possible mid values, pick nodes with value == mid,(after compressing since we don’t know the limit) and update in value index in first Fenwick tree and out value index in second Fenwick tree. Now we can easily calculate how many nodes in the path are with value <= mid and do our conditions.(Let query as {x,y,k} and LCA as l. Calculation part: Fenwick1[in[l],in[x]] — Fenwick2[in[l],in[x]] + Fenwick1[in[l],in[y]] — Fenwick2[in[l],in[y]]. Since in value contains only entry time and out value contains only exit time, the subtraction will remove all the nodes we exited from.
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y,v,l;
};
struct BIT{
vector<int>tree;
int n;
void update(int u,int v){
while(u < n){
tree[u]+=v;
u|= (u + 1);
}
}
BIT(int N):n(N){
tree.resize(n,0);
}
int sum(int v){
int res = 0;
while(v >= 0){
res+=tree[v];
v=(v & (v + 1)) - 1;
}
return res;
}
int query(int l,int r){
int ans = sum(r);
if (l - 1>=0){
ans-=sum(l - 1);
}
return ans;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,m;cin>>n>>m;
vector<int>arr(n);
vector<int>comp;
for (int i = 0;i<n;++i){
cin>>arr[i];
comp.push_back(arr[i]);
}
sort(comp.begin(),comp.end());
comp.erase(unique(comp.begin(),comp.end()),comp.end());
for (int i = 0;i<n;++i){
arr[i] = lower_bound(comp.begin(),comp.end(),arr[i]) - comp.begin();
}
vector<vector<int>>adj(n);
for (int i = 0;i<n - 1;++i){
int x,y;cin>>x>>y;
--x;--y;
adj[x].push_back(y);
adj[y].push_back(x);
}
vector<int>in(n),out(n),depth(n,0);
const int k = 17;
int inf = n;
vector<vector<int>>table(k,vector<int>(n,-1));
int t = 0;
function<void(int)>dfs = [&](int u){
in[u] = t++;
for (auto x:adj[u]){
if (x != table[0][u]){
table[0][x] = u;
depth[x] = depth[u] + 1;
dfs(x);
}
}
out[u] = t++;
};
dfs(0);
for (int i = 1;i<k;++i){
for (int j = 0;j<n;++j){
if (table[i - 1][j] != -1){
table[i][j] = table[i - 1][table[i - 1][j]];
}
}
}
auto LCA = [&](int u,int v){
if (depth[u] < depth[v])swap(u,v);
for (int i = k - 1;i>=0;--i){
if (table[i][u] == -1)continue;
if (depth[table[i][u]] >= depth[v]){
u = table[i][u];
}
}
if (u == v)return u;
for (int i = k - 1;i>=0;--i){
if (table[i][u]==-1 || table[i][v]==-1)continue;
if (table[i][u]!=table[i][v]){
u = table[i][u];
v = table[i][v];
}
}
return table[0][u];
};
vector<vector<int>>pos(inf);
for (int i = 0;i<n;++i){
pos[arr[i]].push_back(i);
}
BIT tree1(t),tree2(t);
vector<int>l(m),r(m),ans(m,0);
vector<node>q;
for (int i = 0;i<m;++i){
int x,y,v;cin>>x>>y>>v;
--x;--y;
q.push_back({x,y,v,LCA(x,y)});
}
vector<vector<int>>needed(inf);
for (int i = 0;i<m;++i){
l[i] = 0,r[i] = inf - 1;
needed[(l[i] + r[i])>>1].push_back(i);
}
bool changed = true;
while(changed){
changed = false;
for (int i = 0;i<t;++i){
tree1.tree[i] = 0;
tree2.tree[i] = 0;
}
for (int i = 0;i<inf;++i){
for (auto x:pos[i]){
tree1.update(in[x],1);
tree2.update(out[x],1);
}
while(!needed[i].empty()){
auto u = needed[i].back();
needed[i].pop_back();
if (tree1.query(in[q[u].l],in[q[u].x]) - tree2.query(in[q[u].l],in[q[u].x]) + tree1.query(in[q[u].l],in[q[u].y]) - tree2.query(in[q[u].l],in[q[u].y]) - (arr[q[u].l]<=i) >= q[u].v){
r[u] = i - 1;
ans[u] = i;
}
else{
l[u] = i + 1;
}
if (l[u] <= r[u]){
needed[(l[u] + r[u])>>1].push_back(u);
if ((l[u] + r[u])>>1 < i){
changed = true;
}
}
}
}
}
for (int i = 0;i<m;++i){
cout<<comp[ans[i]]<<'\n';
}
return 0;
}