Given a weighted undirected tree with N nodes and Q queries. In each query you are given two integers u and v, your task is to find whether all the distinct values which appear on path from u to v appear even number of times. Print YES/NO.

1 \leq N, Q, W[i] \leq 2*10^5

Test case: N = 4, Q = 2, Tree is (u, v, w):

1 2 3

1 3 3

2 4 1

Queries are (u, v):

2 3

3 4

Answer:

YES

NO

In first query, the distinct value is 3 which appears even number of times in first query. However, in the second query, 1 appears odd number of times.

Can anyone help me? **Link is not available since it was a hiring contest problem**. I have one approach but I wasn’t able to code, I was thinking to store number in bitsets and take bitwise xor(will give TLE most probably).

Also I think i have seen this or a similar problem on codechef/codeforces.

@everule1 @ssjgz @carre Please help.