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.
Thanks, got it, totally forgot about this page, used this once before.But is it the best like I don’t remember the time limit but O(Q*sqrt(N)) doesn’t look good. Still, @carre thanks for it.
Notice that, for distinct values, the only thing that matters is that which nodes are equal. So we can map every distinct value onto some 64 bit integer. A good property of randomised values is that, rand()^rand() = rand();. As in, xorring random numbers will still remain equally random. So we can query xor of path of the path, and check if it is 0. Now what is the probability of collisions?
Its on the order of 10^{-14} for 2 \times 10^5 queries.
Fun fact, this can be implemented in O(N + Q) with no complex implementation.
