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.

Please help me to get some of the logic so I can solve it efficiently.

  • $\begingroup$ Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer. For typesetting, please use MathJax. $\endgroup$ – dantopa Jun 9 '19 at 21:26
  • $\begingroup$ What question are you trying to answer? $\endgroup$ – JRyan Jun 10 '19 at 19:14

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<j} |C_i||C_j|$. Then $x=\sum_{v\in P} x_v$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.