Już sobie poradziłem, faktycznie to drzewo przedziałowe wchodzi. Puszczam DFS-a preorder / postorder od korzenia, dla każdego wierzchołka naliczam ile jest wierzchołków w poddrzewie ukorzenionym w nim, i porządek przeglądania tym DFS-em. Robię tablicę vectorów, idx-y wierzchołków o danej wartości, sortuje je własnym operatorem(po tym porządku jak przechodziłem DFS-em) i robię zwykłe drzewo przedziałowe, przeglądam kolor po kolorze, tylko, żeby złożonność się nie zkwadraciła, to muszę jak przeglądne dany kolor to w drzewie przedziałowym nie mogę go clearować całego drzewa przedziałowego, tylko muszę odznaczyć te elementy co zaznaczyłem. Dzięki temu zaznaczę N elementów, i odznaczę N.
O(N lg N), ze względu na sortowanie i operacje na drzewie przedziałowym punkt-przedział.