Techgig coding challenge (finished) and the results are out.Want to know the approach for second question in the contest

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 :
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.


U can use hld(heavy light decomposition),which will basically flatten the tree,then u can use prefix sum /segment tree

Refer this for hld:

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?

1 Like

@meooow The trick of applying all updates together in a tree can also be used in a problem I made, here:

1 Like