https://www.codechef.com/viewsolution/32399872

This is my submission

My logic - used binary lifting to find the LCA of all the given nodes in the set, if LCA is present in the set then print LCA otherwise print -1

works correctly on given test cases, please help where I am wrong in logic or implementation

I also need help in last four questions. Anyone if you can explain then please help me with those last four questions.

For problem E, you can take help from here

and my solution

https://www.codechef.com/viewsolution/32403265

No, you need to first sort the vertices in order of their dfs order, then take consecutive LCA to get LCA of all vertices.

Can you explain how to solve simple LCM ?

but at the end I guess LCA of all nodes will be same if if find out in any orderâ€¦

I am not sure about it but looks like order doesnâ€™t matter in finding LCA

Can you please give me counter example for your statement

Thanks

There should be some problem in your implementation I have used exactly same logic and got AC

https://www.codechef.com/viewsolution/32404229

I can help you in simple modificationâ€¦I did starting A, B, C and E

Isnâ€™t it good enough to check whether there is a unique highest node that is an ancestor of all other nodes?

void dfs(int u, int par)

{

l[u] = ++cur;

ID[cur] = u;

for (int i = 1; i < LN; i++) DP[i][u] = DP[i - 1][DP[i - 1][u]];

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

int v = adjList[u].get(i); //adjList[u][i];

if (v == par) continue;

LVL[v] = LVL[u] + 1;

DP[0][v] = u;

dfs(v, u);

}

r[u] = ++cur; ID[cur] = u;

}

```
int lca(int u, int v)
{
if (LVL[u] > LVL[v]) { int temp=u; u=v; v=temp;}
for (int i = LN - 1; i >= 0; i--)
if (LVL[v] - (1 << i) >= LVL[u]) v = DP[i][v];
if (u == v) return u;
for (int i = LN - 1; i >= 0; i--){
if (DP[i][u] != DP[i][v]){
u = DP[i][u];
v = DP[i][v];
}
}
return DP[0][u];
}
```

use these two functions

in every query take a set store all the vertices and find lca for them one by one

after that check whether final lca is there in the hashset or not

Yeah, exactly. Just check for the one with the least height.

so you mean just using simple intime[] and exittime[] arrays?

I also got E,If you can help with the LCM one and your logic seems correct to me for D maybe there is some problem with the implementation

Yes. Let me finish implementing to check whether it is correct.

It is

yeah looks like i have done some mistake in LCA implementation. I will look into it myself

Can you brief your logic for simple LCM ?

I looked into all 6-7 star guys who got rank from 1 to 5, almost everyone has write O(n^2) solution. I donâ€™t know how they know that it will pass under such constraints