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).
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}
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}
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.
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
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]
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.
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!!
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.
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)
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 ?
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.
Could you please suggest me what to do to reduce time complexity in my approach, Its very little like your approach, CodeChef: Practical coding for everyone 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.
@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? )
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
)
.