Problem statement:
There are N houses in a city connected by exactly N - 1 roads. There is exactly 1 shortest path from any house to any other house. The houses are numbered from 1 to N.
Since Christmas is about to come so Santa has decided to hide gifts in these houses. Santa will come to the city for M consecutive days. Each day he will come to a house a first and will go till house b hiding a gift in each house that comes in the path.
Can you tell the maximum number of gifts any house has after M days.
Input Format First line of input contains 2 integers N - the number of houses in the city and M - the number of days for which Santa comes to the city.
Next N - 1 lines contains two integers u and v meaning there is a road between house u and house v, u != v.
Next M lines contains two integers ai and bi representing the starting and ending house on ith visit of Santa.
Constraints 1 <= N <= 100, 000 1 <= M <= 100, 000 1 <= u, v <= N 1 <= a, b <= N
Output Format A single integer representing the maximum number of gifts in any house.
You can use concept of LCA here . Suppose You are given two Houses X and Y. So the unique path between X and Y will always pass through LCA(X,Y). So Take an array A[] initialized to 0. Now For houses X and Y, First compute LCA using sparse matrix approach(O(logn)). Now Just do :
A[X]+=1
A[Y]+=1
A[LCA(X,Y)]-=1;
if LCA(X,Y) is not the root node just find the parent of LCA(X,Y). Let it be P and then do A[P]-=1. Now just run a dfs taking the sum of all nodes lying in subtree of a given node and just find the node having maximum value which is final answer.
Interesting approach. So as far as I understand the sum of A[v] for all v in the subtree of u gives the number of paths that pass through u.
Can you share some other problems where this is useful or any other resource related to this trick?