Succinct data-structure for nearest colored node in a tree

Abstract

We give a succinct data-structure that stores a tree with colors on the nodes. Given a node x and a color alpha, the structure finds the nearest node to x with color alpha. This results improves the $O(n\log n)$-bits structure of Gawrychowski et al.~[CPM 2016].