At first, let’s take any arbitrary node as the root of the tree.

Let, p[u]=Cost(root,u)p[u] = Cost(root, u) where uu is any node of the tree. We can observe that the Cost(u,v)=p[u]p[v]Cost(u,v) = p[u] \oplus p[v] where uu and vv are two different nodes of the tree. This works because we can write p[u]=Cost(root,L)Cost(L,u)p[u] = Cost(root, L) \oplus Cost(L, u) where LL is the LCA (Lowest Common Ancestor) of node uu and node vv. So, p[u]p[v]=Cost(root,L)Cost(L,u)Cost(root,L)Cost(L,v)=Cost(L,u)Cost(L,v)=Cost(u,v)p[u] \oplus p[v] = Cost(root, L) \oplus Cost(L, u) \oplus Cost(root, L) \oplus Cost(L, v) = Cost(L, u) \oplus Cost(L, v) = Cost(u,v).

It means for each query, if we can calculate p[a]p[b]p[a] \oplus p[b] for all possible a,b(ab)a, b(a \neq b) such that both aa and bb lie on the simple path between node uu and node vv, we can get our desired answer. But how can we do this? Let’s say we store the values of p[a]p[a] for all possible aa in an array FF. Now if we calculate F[i]F[j]F[i] \oplus F[j] for all possible i,ji,j, we get the all possible costs. In this approach Cost(a,a)Cost(a,a) will also be calculated and Cost(a,b)Cost(a,b) will be calculated twice. So, we need to eliminate them later.

But this approach obviously won’t fit within the time limit. Now, what can we do? We can notice that the maximum value of any weight is only 10310^3. We can use this. As p[u]=Cost(root,u)p[u] = Cost(root, u) which is calculated using xor operation and the maximum weight is <210< 2^{10}, the value of any p[u]p[u] will also be <210< 2^{10}. Let’s say the array ff stores the frequency of each element of the array FF. We can apply xor convolution on the array ff with itself using FWHT (Fast Walsh–Hadamard Transform). Then we will get the frequency array of all possible F[i]F[j]F[i] \oplus F[j]. We need to eliminate the count of Cost(a,a)=0Cost(a,a)=0 and double count of Cost(a,b)Cost(a,b) after that. Now if we have this final frequency, we can easily calculate our final answer from that.

For generating the array ff, we can maintain a 2D array cnt[N][W]cnt[N][W] where cnt[u][x]cnt[u][x] stores the frequency of the value xx in p[i]p[i] where ii is any node lies on the path between node uu and the root. Then for any node uu and vv, if we know the LCA(u,v)LCA(u,v) we can easily generate the ff array using the cntcnt array. This is left for the contestants.

Complexity: O(WlogW)\mathcal{O}(W\log{}W) in each query, where taking W=210W = 2^{10} is enough.

Statistics

100% Solution Ratio
NirjhorEarliest, Apr '22
ShadowMeFastest, 0.6s
mumith_fahim99Lightest, 415 MB
mumith_fahim99Shortest, 2476B
Toph uses cookies. By continuing you agree to our Cookie Policy.