Asked in OA - Codeforces

Kvschauhan's blog

Asked in OA

By Kvschauhan, history, 22 months ago, In English

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]

graph, oncampus, codenation

Kvschauhan
22 months ago
12

Comments (10)

Show archived | Write comment?

Kvschauhan

22 months ago, # |

Help!

→ Reply

ROHIT_JAIN

22 months 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.

→ Reply

Tirthsuthar

22 months ago, # |

Which company OA is it? oncampus or offcampus?

→ Reply

Kvschauhan

22 months ago, # ^ |

Codenation

→ Reply

EmilyBloom

22 months ago, # ^ |

placements or internships?

→ Reply

reyaan44

22 months ago, # ^ |

Both.

→ Reply

vrintle

22 months ago, # |

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 <bits/stdc++.h>
using namespace std;

#define int int64_t
#define endl '\n'
#define vi vector<int>
#define vvi vector<vi>
#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<void(int, int)> 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;
	}
}

→ Reply

reyaan44

22 months ago, # |

← Rev. 2 →

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.

→ Reply