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: 55 is also a path with only node 5)
b) Path between node 24 and 42 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 asTP[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, 52, 56, 62,115, 112, 116, 1112, 125, 122, 126}

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, 52, 56, 62,112,116,122, 126} 
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 (NSize[u]).
HenceOut[u] = Size[u]*(NSize[u])
For Node 2 : Out[2] = 5*(145) = 45 > {12, 15, 16. . . . .1411, 1412}
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 thatLvl[Src] > Lvl[Des].
Consider Query as (12,1) then we have path as 12521.
Here, Lca=1 and using FindParent we can find child of Lca in path from Src.
Let it bechild1 = 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 121, 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 Part1Part2Consider 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 (1114),
We can break down it as : Src>Lcaāschild1 , Des>Lcaāschild2 and Lca itself.
Src>Lcaāschild1 will contain nodes 1152 and Des>Lcaāschild2 will contain nodes 1473.
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!!