Intersecting Paths

[l_returns]

find lowest common ancestor ( common grand parent ( or parent) having lowest height)
then use prefix sum over trees to fetch answer of query by dividing it into two queries

i=LCA(a,b)
query(a,b) = find(i,a) + find(i,b)
use pre computed prefix sum in find(i,a) and find(i,b)
https://www.codechef.com/viewsolution/24716158

INTRPATH - EDITORIAL

PROBLEM LINK: Practice Contest: Division 1 Contest: Division 2 Setter: Aman Kumar Singh Tester: Radoslav Dimitrov Editorialist: Teja Vardhan Reddy DIFFICULTY: Medium PREREQUISITES: Math, fast lca queries. PROBLEM: Given a tree containing n vertices. You have to answer following type of queries on the tree Query: given u,v. Find number of unordered pairs (a,b) which have exactly one vertex in common with path (u,v) (Also lets call a path which has only one common vertex with (u,v) is ca…