Top-k Color Queries On Tree Paths

We present a data structure for the following problem: Given a tree T, with each of its nodes assigned a color in a totally ordered set, preprocess T to efficiently answer queries for the top k distinct colors on the path between two nodes, reporting the colors sorted in descending order. Our data structure requires linear space of O(n) words and answers queries in O(k) time