PROBLEM LINK:
Author: Avinash Verma
Editorialist: 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.