COG1806 - Editorial

general
,
1

PROBLEM LINK:

Practice

Contest

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.

Little Appreciation Keeps us Motivated.

2

I solved this problem without Segment tree. We can store the queries for each node, and solve this problem offline in a single dfs.
In dfs, for each node, maintain a map of each depth to its minimum cumulative sum possible in that level.
This is monotonically increasing over depth, so we binary search for the maximum depth with cumulative sum \le query.
Complexity is O((N + Q) log_2(N)).
My solution - 0.10s.

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

3

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 sub-range in merge sort tree.