Tree Problem : Hiring Contest

help
#1

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.

#3

Bro, 1^2^3 = 0. Also your condition is still wrong, remove lca since it is already counted in both 1-u and 1-v so it cancels itself.

#4

what about MO’s algorithm? Check this https://codeforces.com/blog/entry/43230

1 Like
#5

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.

1 Like
#6

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.

4 Likes
#7

Ok, that was a nice trick, thanks.

@everule1 Any proof for this? I think it should be 10^{-9}(Although it’s still very close to 0) but just wanted to understand the maths behind it.

#8

There’s not much to it. The probability of 2 \times 10^5 randomly sampled values from 0, 2^{63} - 1, having a 0, is

1 - \Big(1 - \dfrac{1}{2^{63}}\Big)^{2 \times 10^5}

image
image816×208 23.6 KB