help with my code I have tried storing every distance from special nodes and then calculating the d but It doesn’t seem to be working other than given TC
Can u brief a little bit about ur code?
Can someone please help me in figuring out what’s wrong with the logic?
This is a O(NLogN) solution too, but however i m getting few tle’s and wa’s.
“CodeChef: Practical coding for everyone”
Why in the world is this problem categorized as easy? I mean, does author really think that binary lifting and LCA are “easy” topics? If these type of problems are categorized as easy, I wonder what would hard problems look like.
3 Likes
I have used a simple dfs and bfs to resolve the issue and my code passed all the test cases, i found it difficult using binary lifting so i made it a little simple
https://www.codechef.com/viewsolution/45645840
just a reference to my code
You don’t need binary lifting simple dfs would also suffice.
My dfs only linear time solution
4 Likes
Hey could you explain your code a bit
also what does this mean…int nw_wg = weg - (dist[u] > dist[pos] ? 1 : 1);
You are finding the closest special node and subtracting it with the distance of that closest special node from root A. I guess in this case this does not work. Suppose the closest of node B does not exist in its subtree rather in the different subtree. That way the required distance difference( d(a,u)-d(b,u) ) will be negative whereas we can find a positive distance for a special node that is not nearest but in the subtree of B.
That is some cool stuff
Can you explain your logic
I haven’t even heard binary lifting or LCA before.
CodeChef: Practical coding for everyone I only used dfs
Prerequisites: Binary Lifting, LCA
Difficulty: Easy
That’s really motivating.
2 Likes
hey mahn! can u please explain the code.
A,B \implies described in the question
U \implies Any \ special \ node
L \implies Lca \ of \ U \ and \ B
Basically, we want to maximize the following
D(A,U)-D(B,U)
If we root the tree at node A and re-write the above equation as
D(A,U)-D(B,U)=\cancel {D(A,U)}-(\cancel{D(A,U)}+D(A,B)-2\times D(A,L)) \\
\implies D(A,U)-D(B,U)=2 \times D(A,L)-D(A,B)
So it is clearly evident that we can’t do anything about the second term but we can vary our choice of node U to have different L and hence different D(A,L) values. So we’ll try to maximize that.
Now we can observe that L is a node that lies on the path from the root to node B hence we should try to get the deepest possible node L which has a special node in it’s subtree. That’s it, We’ll pre-compute the special nodes in subtree using one dfs then do a second dfs to calculate the answer for each node.
dfs1 for each node, I assign a value c_i which will be equal to any of the special nodes which is present in the subtree of node i else default value of c_i is zero.
In dfs2 I store all the nodes which lie in the path from root to node i and have a special node in their subtree(in the vector named l in the code) and for computing the answer I just use the formula written above with the last eligible node in the path from root to node i. I kept it brief, feel free to ask if something isn’t clear.
@errormaybe
15 Likes
Hey. I solved it in O(N) only. Don’t know what binary lifting is, but the concept being rooting the tree at ‘a’ and finding depths and subTreeHasSpclNode value in one dfs. Its easy to find solutions for those nodes that have a spcl node in their subtree. For those that don’t, just find the nearest parent that has a subTree with special node, thats it. The second part would need atmost 1 graph traversal again. CodeChef: Practical coding for everyone
2 Likes
hey, Can you explain your code a bit? At least, why did you update that way ?
I can’t figure it out!!!
Thanks!
I rooted my tree on given node (a).
Now for each (b) there will be two scenarios.
- There will be any special node in sub tree of node (b), In this case answer will be distance between node dis(a,b) and any special node below (b).
- If not case 1 then there will be any node on the line of path from (a->b) let say x such that there will be any special node in sub tree of (x), In this case answer will be dis(a,x) - dis(x,b) and any special node in sub tree of x.
For second case we will try to choose a node closest to (b) because dis(a,x) - dis(x,b) will increase as we increase dis(a,x).
For better understanding draw cases on paper.
In my code.
- For distance calculation i simply used a BFS.
- For case 1 handling i used DFS and updated information of every node (x) based on childs responses (The DFS we use for subtree size calculaion).
- For case 2 handling i am using a BFS to store closest node (x) of every node (b).
I hope i made every thing clear, If not please ask.
3 Likes