XOR Tree

shefin Criterion 2021 Round 11

Let's say we have some numbers. In bb-th bit of the numbers, if 1 appears cc times, this bit will contribute (c×2b)(c\times2^b) to the sum of the numbers. That is to say, for each bit bb, if we know how many times 1 appears in that bit, we can easily calculate the sum. This is one of the key observations to solve this problem.

From now on, we will call the special vertex the root of the tree. If the tree has a fixed root uu, we can easily count the number of 1’s in each bit bb of all the values of G(v)G(v). To count them when another vertex will be the root vertex, we can apply the re-rooting technique.

Let's say, we want to switch the root from vertex uu to its child vv. What do we need to do? The effect of vertex uu on the subtree of vertex vv needs to be wiped away. So, if the bb-th bit of AuA_u is 1, the value of bb-th bit of all G(x)G(x)'s will be altered (1’s will be 0’s, 0’s will be 1’s), where xx is any vertex of subtree vv. On the contrary, the effect of vertex vv needs to be added to the whole tree except the subtree of vertex vv (because it has already its effect on its subtree). So, if the bb-th bit of AvA_v is 1, the value of bb-th bit of all G(x)G(x)'s will be altered where xx is any vertex of the tree except the subtree of vv. To switch back the root to vertex uu, just doing these things again is enough due to XOR’s property (find out yourself).

In each time of re-rooting, altering the values of G(x)G(x) will cause TLE. Actually, we don't need to do this. As we need to calculate the sum, we only need to count the number of 1’s in each bit bb of all G(x)G(x)s. Let, there are mm numbers and in bit bb of the numbers, there are kk 1’s. If this bit is altered, the number of 1 in this bit will be (mk)(m-k). We need to use this property. While running DFS, we also need to keep track of if any bit bb of all G(x)G(x)s of the subtree of a vertex vv needs to be altered or not. By managing these, we can easily calculate the new count of 1’s while re-rooting. Re-rooting needs to be done while traversing the tree by DFS.

Complexity: O((V+E)×B)O((V+E)\times B), where BB is the most significant bit of the maximum AiA_i.

P.S: A segment tree (using discovery time in a DFS) with lazy can also be used to alter the bits and count the 1’s. But you may need to be careful about the total number of update and query operations as they may cause TLE.

Contributors

Statistics

86% Solution Ratio
BigBagEarliest, Mar '21
Liad_HossainFastest, 0.2s
serotoninLightest, 32 MB
serotoninShortest, 1333B
Toph uses cookies. By continuing you agree to our Cookie Policy.