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):
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.