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.