Intersecting Paths

Hi All,

Could you please help me with the problem intersectingPath of JUNE Challenge?.

I would request all the coders who have solved the above problem to suggest me the topic to study prior understanding it and request them to re-organize their code by adding comments, re-submit it and please share the submission if possible.

It would be better to get to know about the particular way of dealing with graphs/dp.

Thanks!!

4 Likes

This question easily solved by LCA using euler tour O(1) query,
This is my code:
https://www.codechef.com/viewsolution/24801321

You can read more details about LCA here,

This is also solved by LCA using binary Lifting,

1 Like

Hi @savaliya_vivek could you please help me with the quick explanation?
I am trying to refer to your solution. But stuck with the concept you used to solve.
It would be great help in understanding it you give quick/detailed explanation of your concept.
Thanks.

find lowest common ancestor ( common grand parent ( or parent) having lowest height)
then use prefix sum over trees to fetch answer of query by dividing it into two queries

i=LCA(a,b)
query(a,b) = find(i,a) + find(i,b)
use pre computed prefix sum in find(i,a) and find(i,b)
https://www.codechef.com/viewsolution/24716158

4 Likes

lets consider node u have a,b,c,d adjecent subtree
so,
ans = ab + ac + ad + bc + b* d + c*d + a+b+c+d +1
this equation reduce to,
ans = ((a + b + c + d )^2 - (a^2 + b^2 + c^2 + d^2) )/2 + (a + b+c +d +1)
this can be computed in O(1).

for that ,dfs travelles in tree (consider 1 is root) ,and
for every vertex u store (a+b+c+d) and (a^2 + b^2 + c^2 + d^2) .

f(1,u) = ans of node u based on root 1.
now for query u,v
L= LCA(u,v)
ans = f(1,u) + f(1,v) -f(1,L)
lets, consider cu is child of L (lca) of path L->u and cv is child of L of path L->v
ans = ans + subSize[cu]* subeSize[cv]
here ,subSize[cu] is size of subtree of cu , which is precomputed.

for find cu and cv,

lets index of L in euler tour is X,
cu = query(u,X-1)
cv = query(x+1,v)

7 Likes

Refer this video for understanding the concept of finding LCA.

3 Likes

I solved this problem with heavy-light decomposition of a tree. Heavy-light decomposition - Algorithms for Competitive Programming

Hello Vivek. Can you please make a proper write-up for what you have explained. I cannot understand your answer even when I have already studies LCA. I think it is probably due to your unmentioned assumptions and poor write-up. For example, you haven’t mentioned anywhere what a, b, c and d are. Are those vertices? Are those the number of vertices? Are those the number of adjacent vertices to a particular vertex? Please assume that everyone watching your explanation does not know anything on how to solve the problem, and so try to explain everything in detail. Can you please explain the solution properly, maybe with the help of an example (an example would really help). That would be really helpful. Thank you in advance :slight_smile: .

It’s my bad writing…sorry for that.
a,b,c,d are size of adjecent subtree of vertex u.

In his explanation, a, b, c, d are the sizes of subtrees of its children (read this line again and again if you still don’t get it).

1 Like

Dear @anujsingh14, I understand what you say. But I still don’t get it that by storing these things, how will we reach our answer. I am really sorry I am a bad learner. Perhaps an example can help. Can you please take the same example as given in the test case for this problem and explain what we need to store and how will we use those stored numbers to get our answer. Here is that tree for reference. Suppose we want answers for queries: node 2 to node 3, node 1 to node 2, node 2 to node 5. Also suppose that we root the tree with node 1. Your help will really be appreciated.

Screenshot%20(10)

1 Like

Okay, I will try to help you. I am writing the process of how I approached this problem from the start. (There might and will be some better approaches than mine, but I will try to explain the thought process involved in mine and it will give you the intuition to solve it further).
See, basically after seeing the constraints the first thing that comes in mind is we have to answer each query in O(logn), or maybe O(1). So we need to precompute some values in order to reach this time complexity.
Now, let us arbitrarily root the given tree to 1. We will precompute the number of intersecting paths between the root node (i.e., 1) and any node of the tree and store them in an ans[] array.
How to calculate it? Quite easy!

First of all, calculate the sizes of subtrees of all the nodes and store them in an array sub[](can be done in one dfs).
Now, we will calculate ans[1] i.e., answer of query (1, 1). How?
Let the sizes of subtrees of its children be a, b, c, d (in sample, sizes of subtrees of nodes 3(1), 2(3), 4(1)). The valid intersecting paths must contain 1 in them. So the path between any node from one of the children’s subtree and another children’s subtree will be a valid intersecting path (read this line again and again). For e.g. in sample, Path between node 3 and 4 will be valid, path between node 3 and any node from node 2’s subtree will also be valid, and path between any node from 2’s subtree to node 4 will also be valid, and paths between 1 and any of the nodes in the tree will be valid.
It is easy to see that except the paths originating from 1, they are the sum of product of pairs of sizes of subtrees of children of 1! Let the sizes of subtrees of children of subtrees of children be a, b, c, d. Therefore,
ans[1] = a*b + b*c + a*c + a*d + b*d + c*d + (a + b + c + d) (paths between 1 and any other node) + 1((1, 1) itself).
The sum of product of pairs can be calculated easily during dfs in O(number of children) for each node. Calculate this value for each node during dfs.
Now, to find the number of paths between 1 and any of the nodes, we have to propagate the answer of a parent to its children to get the required answer.
Suppose, we are calculating answer between node 1 and 2 (i.e., ans[2]).
ans[2] initially has the paths consisting of its children’s subtrees only.
Now to get the paths from its parent’s side (its parent is 1), we have to subtract something from its parent’s ans[] value because it will be having some paths which may have more than 1 nodes common with the path 1 - 2. (for e.g, ans[1] will also contain paths like 2 - 1 - 4, which is not required for ans[2]).
Let s = sum of product of pairs (a, b, c, d) + (a + b + c + d). Now what if we want to remove all pairs of d and d itself, how to do that in O(1)? Just subtract the quantity d*((a + b + c + d) - d) - d!
Therefore, to remove the paths like 2 - 1 - 4, we need to subtract sub[2]*(sub[1]-1-sub[2]) - sub[2] (additional minus 1 for getting sum of subtrees of children of 1).
Hence, ans[2] += ans[1] - sub[2] * (sub[1] - 1 - sub[2]) - sub[2])

Hence, answer between root and any of the nodes can be calculated in this way.
Now, I leave the querying part to figure out on your own as an exercise and if you can’t, I will help you, just reply again here.
(Hint: use the precomputed ans[] values and ans[] of LCA!).

My solution: CodeChef: Practical coding for everyone

11 Likes

Thank you so much @anujsingh14. I understood each and every word of what you have written. I have now completely understood how you are storing the answers to queries of the form (1, v) where v can be any vertex. You have also made me understand why is it important to store size of the subtree of every node. But as you might have guessed, it seems that I still have difficulty in querying. One thing I can definitely see is that if user makes a query (u, v), then if ‘u’ is the LCA of ‘u’ and ‘v’, then the answer to this query must contain ans[v] - ans[u]. But I can clearly see that in this process, I am deleting more paths than I should, because ans[u] also included paths where we had to pass through node ‘u’, and it also contained paths which included node ‘u’ and one or more nodes from the path from ‘u’ to ‘v’. I have no idea what should I add to get the correct answer. In addition to this, even if I got the answer to this, I have no clue how can I solve the query of the form (u, v) where the LCA of ‘u’ and ‘v’ is neither ‘u’ nor ‘v’ but something else. You are a real savior and I really thank your efforts brother :smiley:.

2 Likes

One more thing I wanted to add in the previous reply is that I am also maintaining a con[] array where, con[u] denotes its parent’s paths (all possible intersecting paths in the remaining subtree {T - s(u)} , s(u) is u’s subtree and T is whole tree). Hence, con[1]= 0 as it is the root, con[2] = 4.
There will be 4 different cases, I will explain here the most generic one i.e., when lca of (u, v) is none of them. Let that node be named lca.
Let p_u be the node which is an ancestor of u just below lca (read again if you don’t understand), similarly p_v be the node which is an ancestor of v just below lca, in short, p_u and p_v are direct children of lca such that u and v lie in their subtrees respectively.
Now we will break the query (u, v) in 3 parts for ease of calculation:
ans in p_u's subtree + ans in p_v's subtree + contribution of lca. The only thing that will change in the case when lca is either of (u, v) is the contribution of lca part.
For calculation of ans in p_u's subtree: it will simply be ans[u] - con[pu] ! (subtracting contribution of p_u's parent i.e., lca, will disconnect p_u's subtree from remaining tree)
Similarly, for ans in p_v's subtree, ans[v] - con[p_v].
Difficult part is the contribution of lca, and it is as follows :
Now con[p_u] will contain all possible paths in remaining tree except p_u's subtree.
But it will also contain paths in p_v's subtree, which are not desirable as their intersection will give more than one vertices.
So we will subtract p_v's subtree like I mentioned in previous answer on how to remove d from sum of product of pairs of (a, b, c, d) + (a + b + c + d).
Now similarly like this, we have to connect the part {T - S(lca)}.
Try out writing down paths for some pairs in the sample test case using this method, you will get more clarity because it is just maths now for this querying part.
Refer my solution for implementation details.

6 Likes

Really, good effort.
Nice explanation :smiley::smiley:

1 Like

Thanks for explanation of this approach.

2 Likes

If anyone’s still stuck, take a look at my explanation!

1 Like

Thank you so much @anujsingh14. I have successfully submitted my code and got AC. Thank you again for your help and time. I appreciate it a lot. If anyone wants, he/she can have a look at my solution CodeChef: Practical coding for everyone. Kudos to the ones explaining the solutions of problems.

1 Like

Very happy to help :slight_smile:
Just one more suggestion, keep your variable names short and concise as it will then be better to debug the code afterwards.

1 Like