# Finding number of pairs of vertices in a graph such that the path between them has only one vertex common with a different given path

Given a tree with N vertices and N-1 undirected edges. 1<=N<=250000 There are certain queries to be performed. 1<=Q<=10^5 In each query we will be given two vertices,say a and b. We have to tell the number of pairs of vertices such that the path between those contain exactly one vertex common with the vertices present in the path between the vertices a and b. For example: N=6.So N-1 edges.--> 1 2, 1 3, 1 4, 2 5, 2 6. (Meaning 1 is connected to 2,3,4 and 2 is connected to 1,5,6)

Let our query be a and b--> 4 5.

Answer will be 6.(Means there exist 6 pairs of vertices in the graph with the given condition) Those 6 pairs are: 1 1, 2 2, 4 4, 5 5, 1 3, 2 6.

I have been thinking this question for 2 days but I am not able to get any perfect logic for this. I first thought that we can find by using LCA (lowest common ancestor) but then I could not find how.

Let $$V$$ be the set of the vertices of the given tree $$T$$ and $$P$$ be the unique path in the tree between $$a$$ and $$b$$. We can compute the required number $$x$$ of the pairs as follows. For each vertex $$v\in P$$ let $$T_v$$ be the subgraph of $$T$$ induced by the set $$(V\setminus P)\cup\{v\}$$ and $$T’_v$$ be a connected component of $$T_v$$ containing $$v$$. Let $$C_1,\dots, C_k$$ be the connected components of $$T’_v\setminus\{v\}$$ and $$X_v=\sum_{i. Then $$x=\sum_{v\in P} x_v$$.