# C++ solution using binary lifting and map

#1
``````vector<int>height,parent;
vector<vector<int>> node;
map<pair<int,int> , int> wt;

void build(int root ,int h,int par){
height[root] = h;
parent[root] = par;
for(int i : node[root]){
if(i==par)continue;
build(i,h+1,root);
}
}

int cal(int u, int v){
int ans = 0;
while(height[u]>height[v]){
ans = max(ans,wt[{u,parent[u]}]);
u = parent[u];
}
while(height[u]<height[v]){
ans = max(ans,wt[{v,parent[v]}]);
v = parent[v];
}
while(u!=v){
ans = max(ans,wt[{u,parent[u]}]);
ans = max(ans,wt[{v,parent[v]}]);
u = parent[u];
v = parent[v];
}
return ans;
}

vector<int> Solution::solve(vector<vector<int> > &A, vector<vector<int> > &B) {
int n = A.size()+1;
node = vector<vector<int>> (n+1);
for(auto i : A){
node[i[0]].push_back(i[1]);
node[i[1]].push_back(i[0]);
wt[{i[0],i[1]}] = i[2];
wt[{i[1],i[0]}] = i[2];
}
height = vector<int> (n+1,-1);
parent = vector<int> (n+1,-1);
build(1,0,0);

vector<int> ans;

for(int i = 0;i<(int)B.size();i++){
int u = B[i][0];
int v = B[i][1];

ans.push_back(cal(u,v));
}
return ans;
}
``````

#2

this is not binary lifting.
Your solution passed because of weak test cases.
consider a case where tree is like a linked list.