Amazon OA question related to LCA( binary lifting)

                                                        AMAZON ONLINE ASSESSMENT
/*

You are given the following:-

A tree consisting of N nodes, where every node holds either a zero or one value. You are given u and v and a string S is generated as a binary string which represents the path between u and v. You are also given a vector A representing the value of ith(1-based) node.

A GOOD string is a string where the count of "01" substring is equal to the count of "10" substring. A operation consists of flipping the bit, i.e. 1 becomes 0 and vice versa.

TASK-
Determine the minimum number of operations required to convert string S into a GOOD string. You are given Q queries of the form
[u , v]. Determine result for each

Example

N=5
Edges = [(1,2),(2,3),(3,4),(4,5)]
A = [0,1,0,1,1]

Query 1 is given as 1 5 denoting nodes u and v respectively. The simple path between node 1 and node 5 is 1-2-3-4-5. String S generated is 01011. You change the last value in the string to 0. String S becomes 01010. In the new string formed, both 01 and 10 occur 2 times which is equal. 1 operation is required to convert string S into a GOOD string, and therefore, the answer is 1.

Query 2 is given as 1 3 denoting nodes u and v respectively. The simple path between node 1 and node 3 is 1-2-3. String S generated is 010. In this string, both 01 and 10 occur an equal number of times. 0 operation required to convert string S into a GOOD string, and therefore, the answer is 0.

Constraints- N = 2 ≤ N ≤ 2 * 10^5
             Q = 2 ≤ Q ≤ 2 * 10^5

Complete the given function having parameters, edges, N, A, Q
*/

/*--------------------------------------------------------------------------------------------------------------------------------*/
                                                                    THOUGHT PROCESS

This is really a nice question. I believe its a combination of two different problems

Problem 1:-
How will you efficiently find path between u->v because traditional BFS/DFS would surely result in TLE for that ridiculous          constraint?

ANSWER-> Use binary lifting to find LCA of u and v first. Precomputation takes n*logn. But after that you will be able to find LCA in logn time. After finding LCA, your path string is reverse(LCA->u)+LCA->v. This is a lot better than just doing DFS from u to v, as DFS will take N time, while this method will just take O(h) time where h is the height of LCA from leaf node

Problem 2:-
How are you finding the minimum operation require to make GOOD string?

ANSWER-> Actually this is where we do not need any time!! Yes, the TC is O(1). All you need to do is check first and last character, if both of them are different, return 1 , else 0. It is basically a simple observation. So you literally did this in O(1) time. Don't believe me, here are some examples, please check the first and last character as I said,
1100001 = 0
1010101 = 0
1000001 = 0
0110010 = 0
1010100 = 1
0110101 = 1

SO BASICALLY THIS QUESTION WAS TESTING YOUR KNOWLEDGE OF LCA AND HOW EFFICIENTLY YOU CAN DO IT!!!

TIME COMPLEXITY-
N * logN to precompute.
Q * max( logN, H ) where H is the max height of tree, incase of linear tree.


=> CRAZY=> Now, GIVE IT A GOOD THOUGHT. Do you think we even need the path when all we check if the last and first character of the path string..HAHAHA..No, just check A[u]!=A[v] then 1 or 0. So code complexity becomes O(Q). Lmao!!!! Anyways I would still advise you to go through the code below to understand this idea of LCA used in path finding. Might be useful somewhere in the future...

/*--------------------------------------------------------------------------------------------------------------------------------*/

CODE BELOW-

#include <bits/stdc++.h>
using namespace std;

int dp[200005][20];
vector<int> parent;
vector<int> height;
vector<int> adj[200005];
vector<char> values;


void initialize(int n, vector<vector<int>> &edges){
    parent.resize(n+1);
    height.resize(n+1,0);
    for(auto edge: edges){
        adj[edge[0]].push_back(edge[1]);
        adj[edge[1]].push_back(edge[0]);
    }
}


void dfs(int node, int par, int d){
    parent[node]=par;
    height[node]=d;
    for(auto nei: adj[node]){
        if(nei!=par){
            dfs(nei,node,d+1);
        }
    }
}

void pre_compute(int n){
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++){
        dp[i][0]=parent[i];
    }
    for(int i=1;i<=n;i++){
        for(int jump=1;jump<20;jump++){
            if(dp[i][jump-1]!=-1){
                dp[i][jump]=dp[dp[i][jump-1]][jump-1];
            }
        }
    }
}

void moveUP(int &node, int k){
    for(int jump=19;jump>=0;jump--){
        if(k>=pow(2,jump)){
            k-=pow(2,jump);
            node=dp[node][jump];
        }
    }
}

int LCA(int u, int v){
    int heightU=height[u];
    int heightV=height[v];
    if(heightU>heightV){
        moveUP(u,heightU-heightV);
    }
    if(heightV>heightU){
        moveUP(v,heightV-heightU);
    }
    if(u==v){
        return u;
    }
    for(int jump=19;jump>=0;jump--){
        if(dp[u][jump]!=dp[v][jump]){
            u=dp[u][jump];
            v=dp[v][jump];
        }
    }
    return dp[u][0];
}

string getPath(int u, int v){
    int lca=LCA(u,v);
    string u_lca="";
    while(u!=lca){
        u_lca+=values[u];
        u=parent[u];
    }
    u_lca+=values[lca];
    string v_lca="";
    while(v!=lca){
        v_lca+=values[v];
        v=parent[v];
    }
    reverse(v_lca.begin(),v_lca.end());
    return u_lca + v_lca;
}

int convertOps(string &str){
    return str[0]!=str[str.size()-1];
}

int main(){
    int n = 8;
    vector<vector<int>> edges = {{1, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {3, 7}, {3, 8}};
    values = {'#', '1', '0', '1', '1', '0', '1', '0', '1'};
    vector<vector<int>> queries = {{1, 6}, {3, 7}, {1, 5}, {7, 8}, {4, 6}};
    initialize(n,edges);
    dfs(1,-1,0);
    pre_compute(n);
    for(auto q: queries){
        string path=getPath(q[0],q[1]);
        int ops=convertOps(path);
        cout<<ops<<endl;
    }



    // int n=5;
    // vector<vector<int>> edges={{1,2},{2,3},{3,4},{4,5}};
    // values={'#','1','0','1','0','1'};
    // vector<vector<int>> queries={{1,5},{4,5},{1,5}};
    // initialize(n,edges);
    // dfs(1,-1,0);
    // pre_compute(n);
    // for(auto q: queries){
    //  string path=getPath(q[0],q[1]);
    //  int ops=convertOps(path);
    //  cout<<ops<<endl;
    // }
}