Please subscribe to the official Codeforces channel in Telegram via the link ×

[Need Help] Order statistics in rooted trees

Revision en2, by skavurskaa, 2016-04-24 02:44:44


I am solving a problem where a rooted tree with N vertices is given, each vertex has a value V <= 10^9, and i have to answer M queries. Each of the queries has the format (V,K), and i have to answer which is the K-th smallest value in the subtree rooted in vertex V. The limits for N,M are 10^5.

My current approach solves almost every instance of the problem (O(N log N) average) but fails when the tree degenerates to a linked list (O(N^2 log N) worst case). I store every query so i can answer all them after i run my algorithm. I process the tree from the leaves up to the root using topological sort, and when i am processing some vertex, i merge the leaves' subtrees values using heapsort (found it to be faster than mergesort, but still slow if the tree is a linked list), and answer every query related to this vertex. After every vertex has been processed, i iterate over the answer array and print the results.

Can anyone help me with a better approach, or point some property that can help my solution so it doesn't get TLE verdict?

Thanks in advance.

EDIT : problem solved, used the idea given by ffao.

Original statement :

My code :

Tags graph, trees, k-th order statistic


  Rev. Lang. By When Δ Comment
en2 English skavurskaa 2016-04-24 02:44:44 201 problem solved
en1 English skavurskaa 2016-04-23 20:22:43 1125 Initial revision (published)