That's the same idea I used, AC on the first go

You can solve it without using heavy-light decomposition.

At first make 1st vertex the root of the tree.

Let's imagine you can get for every x and v the amount of vertices with assigned value equal to x on the path from root to v. Let's call this function get(v, x).

And now how to answer for a query a, b, x? Let c = lca(a, b) and d = ancestor(c). Then, the number of times when number x appears on the path from a to b equals to get(a, x) + get(b, x) — get(c, x) — get(d, x) = get(a, x) + get(b, x) — 2 * get(c, x) + 1 if value[c] == x. If this value > 0 then the answer is "yes";

And now, how to calculate get(v, x)? For every vertex v we will keep persistent array cnt (= persistent segment tree) where cnt[x] = number of vertices u with value[u] == x on the path from 1 to v. How to get this array for node v? Just take this array from ancestor(v) and increase cnt[value[v]] by 1

Let's solve a simpler version of this problem.

We are given an array full of zeroes.

We define two queries:

QUERY 1: UPD(x,c) — A[x] = c

QUERY 2: Q(a,b,c) — See if there is a number c between [a,b]

All queries are sorted by c in increasing order, breaking ties with the query type (QUERY 1 goes first)

RULE: Note that, when we must answer queries of type 2, the array will ALWAYS have elements A[i] <= c, never greater.

Now, let's say that, for a given Query Q(a,b,c), the maximum element between [a,b] is M. If M < c, then we can be sure that there isn't any c in this interval (given by the RULE). Otherwise, there is a number c somewhere (and that's enough because we don't care about its position).

How to find efficiently the maximum element in an interval? (Segment Tree cough)

What about another kind of problem?

In this new problem we have only Queries of type 2, our array is not neccesarily full of zeroes, and the queries are not sorted by c.

Piece of cake! We can transform this problem to the first problem I described previously!

We can say each position of our input array will be Queries of type 1, and then sort all the queries! This way, we are answering the queries OFFLINE.

Now, this solution can be applied to this problem. You can use Heavy Light Decomposition with Segment Tree to answer RMQ. Use the node labels as queries of type 1

Good luck! :)

You can solve it using Persistent Segment Tree :).