Unofficial INTRPTH Editorial/Explanation

Problem : INTRPATH (JUNE 19)
Problem Link : https://www.codechef.com/problems/INTRPATH
Prerequisite : DFS , LeastCommonAncestor.

Before starting I would like to give an overview of problem. Given 2 nodes (Src and Des) , we have to find the total number of paths which will contain only 1 node common with the path from Src to Des.

Here we will assume that the tree is always rooted at node 1. Also for every node across the tree we will find Lvl[N], Size[N], Par[N] which will store the Level, Size and Parent of each node.
Note: a) Path can contain only one node (For ex: 5-5 is also a path with only node 5)
b) Path between node 2-4 and 4-2 is consider as one path (cuz of Undirected graph).

  1. Total Number of Paths which can be formed inside a subtree of a node. TP[u]: This is same as selecting any two nodes present inside the subtree and there will exist a path between them plus size of Subtree. (Note a)

    Total Paths = nCr + n ;where n=Size of node and r=2.
    which is same as TP[u] = Size[u]*(Size[u]+1)/2 . For Node 2 =TP[2]= (5*6/2) = 15 Paths.
    TP[2] = 15 -> { 2,5,6,11,12, 5-2, 5-6, 6-2,11-5, 11-2, 11-6, 11-12, 12-5, 12-2, 12-6}

  1. Total Number of Paths which passes through node u and are inside subtree IN[u] :This thing is nothing but (Total paths formed inside ‘u’ - Total paths inside which do not pass through ‘u’).
    Total paths formed inside Child of ‘u’ will remain in child and never pass through ‘u’.
    Hence, IN[u] = TP[u]-(TP[c1]+Tp[c2]+....+TP[cn]) where c1,c2,cn are children of u.
    For Node 2 : IN[2] = 8 = TP[2] - (TP[5]+TP[6]) -> {2, 5-2, 5-6, 6-2,11-2,11-6,12-2, 12-6}

  2. Total Number of Paths which passes through node u and are outside subtree OUT[u] :
    For this one node must come from inside ‘u’ and the other from ouside ‘u’. Can you tell how many nodes are present outside ‘u’? Yes!! It is nothing but (N-Size[u]).
    Hence Out[u] = Size[u]*(N-Size[u])
    For Node 2 : Out[2] = 5*(14-5) = 45 -> {1-2, 1-5, 1-6. . . . .14-11, 14-12}

If you are clear with the above points, you can move ahead else read couple times. :slight_smile:
The above things can be precomputed for every node in a single dfs. If you are familiar with LCA and how to find Parent of node at Distance ‘d’ then continue reading. Else take a glance at those things and come back. Now the Question can be broken down into three parts.
Let Lca = lca(Src,Des) and Ans=0

  1. Case a : When Src is same as Des -> Think a bit…and if u have ans as IN[src]+OUT[src] you got it right. Total Paths passing through a single node is : Ans = IN[src]+OUT[src]

  2. Case b : When Src /Des is LCA -> Whenever we will have Src as LCA we can swap(Src,Des) so that Lvl[Src] > Lvl[Des]. Consider Query as (12,1) then we have path as 12-5-2-1.
    Here, Lca=1 and using FindParent we can find child of Lca in path from Src.
    Let it be child1 = FindParent(Src, Lvl[Src]-Lvl[Des]-1). child1=2 in this path.

  • No. Ways For Src Node = For Src node none of the path can come from outside as it will apparently pass from its parent node which is also in our path. Hence
    Ans = IN[Src]

  • No. Ways For Des Node = For Des Node we can simply substract the paths coming from its child which is in our path. Total paths to substract will be equal to OUT[child1]. Read Note b.
    Ans += IN[Des]+OUT[Des]-OUT[child1]

  • No. Ways For Intermediate Node = In our path 12-1, Nodes 5 and 2 are intermediate nodes.
    In this case no path will come from outside as above. So for a node ‘u’, it will be Total paths
    passing through ‘u’ inside it discarding Total paths coming from its child. For discarding part, one
    end must come from its child and other from the Subtree of ‘u’ neglecting this child.
    Ans += IN[u]-Size[child]*(Size[u]-Size[child]). Let’s consider it as Part1-Part2

    Consider Node 5 : Ans += IN[5] - Size[12] *(Size[5]-Size[12])
    Consider Node 2 : Ans += IN[2] - Size[5] *(Size[2]-Size[5])

Calculating above part for each intermediate node will be time consuming and hence we need
an optimized way for dealing this. For every node we can store Prefix Sum for Part1 and Part2 by considering a path to that node from root node. In this way we can answer above query in constant time. It will require single dfs to calculate for each node. I want you to try this part by yourself cuz you’ll learn a new way which will be useful very often. Try it else ask again. :slight_smile:

  1. Case c : When LCA is b/w Src and Des -> This is the last case and we have already solved the half of it’s part. Consider query (11-14),
    We can break down it as : Src->Lca’schild1 , Des->Lca’schild2 and Lca itself.
    Src->Lca’schild1 will contain nodes 11-5-2 and Des->Lca’schild2 will contain nodes 14-7-3.
    These both parts are same as case b and We can find them using exact logic!! The only difference will be the Lca’s child will also act as an intermediate node.
    And For Lca part We will need to find the possible ways passing through Lca discarding the paths coming from it’s 2 child. It is somewhat same as case b.ii)
    Ans = IN[Des] + OUT[Des] - OUT[child1] - OUT[child2];
    Ans += Size[child1]*Size[child2]
    We need to add product of sizes of it’s two child because while substracting their OUT[child1] and OUT[child2] we are deleting the paths from child1 to child2 two times.

Any kind of Questions/Corrections/Suggestions are most welcomed!! :slight_smile:

23 Likes

Great Explanation!!
A link to your solution will be more helpful

1 Like

My Solution.

1 Like

Can you explain what DFS2 is doing. Pre_in and Pre_sub?
And what importance they are playing ?

They are storing the Prefix Sum of Case b.3 by considering the path from root Node. Pre_IN is storing Prefix sum of Part1 (follow explanation) and Pre_Sub of Part2. You can there by calculate no. of ways for all Intermediate node in a O(1) time.

1 Like

why is this required in case 3 ? can you please elaborate ?

while substracting in equ above,
-OUT[c1] (it will also delete paths coming from child 2 and its Subtree)
-OUT[c2] (it will also delete paths coming from child 1 and its Subtree)

The both paths i have written in bracket are the same thing.
and we are deleting them twice. Hence in order to
compensate we have to add those paths (i.e Sub[c1]*Sub[c2] or paths from c1 to c2 or vice versa)

1 Like

Yeah thanks I understand the logic now…

1 Like

Can someone tell me what’s this array P[N][LG] for ???

This array is basically used for finding lca of node. It keep details of all the ancestor of that node…

Refer the last part for detail explanation.

2 Likes

I am not able to understand following lines…
ans += In[NodeBfrDes1]-(Sub[NodeBfrDes2] * (Sub[NodeBfrDes1]-Sub[NodeBfrDes2]));

and

ans += In[NodeBfrDes3]-(Sub[NodeBfrDes4] * (Sub[NodeBfrDes3]-Sub[NodeBfrDes4]));
Can somebody please explain this with respect to author’s code?

1 Like

Here, We need to find ways for Lca’s child. So, now my Des is Lca’s child.
Now no. of ways for Des will be same as case b.iii) .And those are the
ways of passing through a node ‘u’ neglecting the paths coming from
single child. Becuz Lca’s child is also an intermediate node. so
NodeBfrDes1 = Lca’s child (node ‘u’ in case b.iii)
and NodeBfrDes2 = Lca’s child’s -> child (node ‘child’ in case b.iii).
I guess i should have mention it in editorial!!

You understood the problem very well, I’m still having a hard time understanding this part. Can you please explain it with the help of some examples ?

I appreciate your explanation. Your solution is very readable and easy to understand. You have made a really nice editorial. Good job!

1 Like

Okay. Consider path 11-13. So we have Src=11, Des=13 & Lca=1. Now we can break it as,
i) Src to Lca’s child (11 to Node 2).
ii) Lca.
iii) Des to Lca’s child (13 to Node 3).

For i) Src=11 Intermediate Node=5 and Des=2.
For 11, Ways we will consider which are only coming from it’s subtree(Becuz any ways from outside will pass thru it’s parent i.e Node 5).
For 5, Ways we will consider which are only coming from it’s subtree(Becuz any ways from outside will pass thru it’s parent i.e Node 2) and discarding the paths coming from it’s child
i.e node 11.
For 2, Ways we will consider which are only coming from it’s subtree(Becuz any ways from outside will pass thru it’s parent i.e Node 1(Lca)) discarding the paths coming from it’s child
i.e node 5.
So you can see unlike case b.2) in my explanation the des node is also acting as an intermediate node.

For ii) Lca=1 we will consider all paths neglecting paths coming from Node 2 and 3 and their subtrees.

For iii) Same as i)

1 Like

Could you please suggest me what to do to reduce time complexity in my approach, Its very little like your approach, https://www.codechef.com/viewsolution/24839368 is my solution, kindly have a look into it, and suggest me any improvements

I will explain my approach, first, here I always take node 1 as root and I also have node 0 as a proxy root of all.
So, first of all, I add u,v and v,u to the graph adj ArrayList, also in the ArrayList, I have its own element as the last one. Like for 1 -> it will be 2,3,4,1 (Suppose), and for every node in the graph, I have another variable called depth (Or the number of nodes in the subtree including the parent).
Then most of the nodes in the Adj ArrayList are updated and the rest which is not being handled can be updated by do-Update() function.

Next, for every Query, I find the path between those nodes given and insert the nodes in the path into “ares” ArrayList.

Then for every node in the ares or path, I call pythagoreanUtil() function (Ignore the name), and in that comes main part of the question
Let’s consider the path as 1 to 2 (Using your picture), Here the number of paths through 2 are 31 + 3 + 1; that is the number of nodes in one subtree multiplied with another subtree and number of individual paths coming from these subtrees. Then for 1, it’s 44 + 4 +4 and then finally the number of nodes in the original Ares ArrayList that is 1 and 2 so 33 will be the final answer.

If there are more than 2 subtrees for a node, what to do, then suppose 2 has 3 subtrees of sizes 3, 4, and 2 then I have to multiply each of them once for every element that is 34+3+4 and 32+3+2 and 4*2+4+2 will give number of paths through 2.

Please look into the solution and suggest any solution ASAP.
If you find any mistakes or even blunders in my theory please clarify.

1 Like

@mattadevaraj
Your solution is absolutely correct but not optimized. Let’s consider u have
found a formula which will find the ways for every single node present in our query.
Then time require for Src = O(1) and Des = O(1) and For NodesBetw = O(x) where x is no. of nodes
in b/w Src and Des. In worst case ‘x’ can be approx equal to N (N=250000, For skewed tree).
It is clear that we will require O(N) time for each query. So total time = O(N*Q), where Q = 300000;
We can’t do better cuz we will have to reach every node anyhow.

Now, As per above explanation, using cummulative sum we can calculate ways with O(N) precomputation and
for NodesBetw in O(1) for each query, So total time = O(N*1); (isn’t it cool, huh? :smiley:)
Here we don’t even need to visit every node in between and that’s what makes it more optimized.
You can check my soln which gave me max 30 pts similar to urs. - Solution

1 Like

@idgaf18 Thanks again ! man you are really helpful now I understand the solution completely . thank you once again :smiley: .