PROBLEM LINK:Author: Avinash Verma DIFFICULTY:MEDIUM PREREQUISITES:DFS, Euler Tour and Merge Sort Tree PROBLEM:Calculate the maximum length of the sequence in a tree such that every node is a child of previous node and sum of the capacity of nodes in the sequence should be less than S. QUICK EXPLANATION:First change the nodes value i.e $A[u]+=A[parent[u]]$ ,where $parent[u]$ is parent of u,then use concept of segment tree on rooted tree and merge sort tree to find the node in the subtree of X such that A[node] is less than or equal to $ S + A[parent[X]] $, then the path between X and node that you found. EXPLANATION:Convert every query for node X to query for whole tree. Apply DFS on the tree to calculate depth of each node in tree and calculate cumulative sum of every node from top to bottom i.e $ A[u] = A[u] + A[parent[u]] $. So, for each query of node X and S sum. We add value of $A[parent[X]]$ to $S$, then we want to find a node d in subtree of node X such that $A[d]$ is less than or equal to S and depth of d is maximum. So, answer is length between node X to node d. Why? To convert subtree query to range query. We will make a Euler tour of the tree. Then for each query, we have to find the node of maximum depth in range of particular subtree range, Such that sum of capacity of path from X to that particular node is less than S. To find a node such that $A[node]$ in subtree of node X, is less than S and have maximum depth. We will create a merge sort tree of Euler path of tree store in pair value format i.e pair of $A[node]$ and $depth[node]$. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 25 Nov '18, 18:21

I solved this problem without Segment tree. We can store the queries for each node, and solve this problem offline in a single dfs. PS: In your solution, you store $pair(cumsum, depth)$ for each subtree. How can you binary search on the largest depth with $cumsum \le query$ with this information, since for same depth, there can be multiple sums associated? @avi892nash answered 26 Nov '18, 14:35

I am storing pair(cumsum, depth) for every node in the tree. So, Let's consider we want to find a sequence with starting node 1 i.e. root, then we will find the maximum depth of any node such that cumsum ≤ query. This can be done in a loop. But if we sort the pair values then make a new array P of same length as of pair values such that P[i] is equal to maximum depth of all sorted pair values from 0 to i. So, for any value of S in query. We have to find maximum index of sorted pair values such that cumsum ≤ query, then P[index] will gives us the maximum depth of a node having cumsum ≤ query. You have to create P[] for all subrange in merge sort tree. answered 27 Nov '18, 03:16
