Kvschauhan's blog

By Kvschauhan, history, 6 weeks ago,

Given a tree with A nodes given in form of 2D array B, where each row consists of 2 integers denoting the presence of an edge between the two integers. Also given another 2D array C of Q queries, each row consists of 3 elements — U, V, and W. Find out the closest node to W on the path from U to V(Path means a subtree in the form of the line containing U, and V as endpoints ). Process each query and return the answer to each query.

Constraint:- 2<=A<=100000 1<=Q<=100000 1<=B[i][0],B[i][1]<=N, B[i][0]!=B[i][1] |B|=A-1 1<=U,V,W<=N(U!=V)

Input 1:- A=6 B=[[1,2],[1,3],[1,4],[3,5],[3,6]] c=[[2,5,6],[5,2,6]]

OUTPUT1:- [3,3]

Input 2:- A=6 B=[[1,2],[1,3],[1,4],[3,5],[3,6]] c=[[2,5,1],[2,5,4]]

OUTPUT2:- [1,1]

• +12

 » 6 weeks ago, # |   +3 Help!
 » 6 weeks ago, # |   +15 Let's rooted the tree at node 1.Then calculate the following:- LCA of U and W :-> x LCA of V and W :-> y LCA of U and V :-> z (LCA is Lowest common ancestor.)Now there will be 2 cases:-case1:- x=y. In this case z will be our answer.case2:- x!=y. In this case if x!=z then answer will be x else answer will be y.
 » 6 weeks ago, # |   0 Which company OA is it? oncampus or offcampus?
•  » » 6 weeks ago, # ^ |   0 Codenation
•  » » » 6 weeks ago, # ^ |   0 placements or internships?
•  » » » » 6 weeks ago, # ^ |   0 Both.
 » 6 weeks ago, # |   +1 Nice problem, but a bit standard if you know about LCA.ROHIT_JAIN explained it really well, and here is my solution for the same: https://ideone.com/r4bB3U Spoiler#include using namespace std; #define int int64_t #define endl '\n' #define vi vector #define vvi vector #define each(a) for(auto& e: a) #define rep(n, i) for(int i = 0; i < n; i++) void solve() { int n; cin >> n; vvi G(n), dp(n, vi(20)); rep(n - 1, _) { int u, v; cin >> u >> v; u--; v--; G[u].push_back(v); G[v].push_back(u); } vi tin(n), tout(n); int t = 0; function dfs = [&](int i, int p) { if(p != -1) { dp[i][0] = p; for(int j = 1; j < 20; j++) { dp[i][j] = dp[dp[i][j - 1]][j - 1]; } } tin[i] = t++; each(G[i]) { if(e != p) dfs(e, i); } tout[i] = t++; }; dfs(0, -1); auto is_ancestor = [&](int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }; auto lca = [&](int u, int v) { if(is_ancestor(u, v)) return u; if(is_ancestor(v, u)) return v; for(int j = 19; j >= 0; j--) { if(!is_ancestor(dp[u][j], v)) u = dp[u][j]; } return dp[u][0]; }; auto get_descendant = [&](int u, int v) { if(is_ancestor(u, v)) return v; return u; }; int q; cin >> q; while(q--) { int u, v, w; cin >> u >> v >> w; u--; v--; w--; int ans = lca(u, v); ans = get_descendant(ans, lca(u, w)); ans = get_descendant(ans, lca(v, w)); cout << ans + 1 << endl; } } int32_t main() { int t = 1; cin >> t; while(t--) { solve(); cout << endl; } } 
•  » » 6 weeks ago, # ^ |   0 Thanks man!! Could you please provide link of any resource for this algorithm.
 » 6 weeks ago, # | ← Rev. 2 →   0 I can think of 3 cases here :- If both U and V are in subtree of W : LCA(U,V) If either U or V is in subtree of W and other is not : W If neither U nor V is in subtree of W : Do Binary Lifting on W till either U or V comes in subtree of W, whenever it gets first, that node will be the answer. To find out whether a node X is in the subtree of node Y or not in constant time, you can use Euler Tour, or If you are okay with O(Logn), then you can apply binary lifting on X till it reaches the depth of node Y.
•  » » 6 weeks ago, # ^ |   0 In case 3 when u or v is in subtree of lifted W. Then we have to find the answer by solving with logic of case 1 or case 2, right?Obviously, lifted W is not always going to be on the u-v path. Example
•  » » » 6 weeks ago, # ^ |   0 Yes, Correct.
 » 6 weeks ago, # |   0 Nice question