#E
题意：给定一颗由n个点组成的树，第i个点的的权值
，同时给定所有边权，边权为两个点的异或值，求有多少中满足要求的点权组合。
思路：当任意一个点的权值确定后，所有的点的权值也就通过边权间接唯一求出。
不妨设![a[1]=0](https://www.nowcoder.com/equation?tex=a_%7B1%7D%3D0 "a[1]=0")
,进而推出所有点的权值，当![a[1]=x](https://www.nowcoder.com/equation?tex=a_%7B1%7D%3Dx "a[1]=x")
时,![a'[i]](https://www.nowcoder.com/equation?tex=a'_%7Bi%7D%3Da_%7Bi%7D%20%5Coplus%20x "a'[i]")
, 又因为![a'[i]的范围](https://www.nowcoder.com/equation?tex=a'_%7Bi%7D%5Cin%20%5Bl_%7Bi%7D%2Cr_%7Bi%7D%5D "a'[i]的范围")
可以推导出
。所以问题就是求有几个x满足题意。
如何解决这个问题，让我们请出Kur1su。
我们把求x的问题考虑成有多少点被覆盖了n次。因为点有很多个，我们把它们看成区间**[a,b]。每次覆盖的时候就给a打上一个1标记，给b+1打上一个-1标记。对于区间[0,a-1]这一段的标记是0**，[a,b]为1，[b+1,inf]又为0。如此一来我们可以把覆盖区间**[a,b]转换成对给区间[1,a-1]打上-1标记,[1，b]打上1**标记。
对于
我们先打**-1标记，后打1标记，反之，对于另一部分，先打1标记，后打-1标记。我们按位搜索，一共四种情况，00,01,10,11前面是a[i]，后面是l[i]-1或者r[i]。
当是00时，我们目前已经有0**，实际也需要0,0^0=0，我们可以知道现在的前缀大小不会发生改变，也不会有区间被覆盖。
当是01时，我们目前已经有0，实际也需要1,0^1=1，我们可以知道现在的前缀大小会加上2^pos，区间[now , now+(1<<pos) - 1]被覆盖。
当是10时，我们目前已经有1，实际也需要0,1^0=1，我们可以知道现在的前缀大小会加上2^pos，但是却没有区间被覆盖。
当是11时，我们目前已经有1，实际也需要1,1^1=0，我们可以知道现在的前缀大小不变，区间[now+(1<<pos) , now+( 1<<(pos+1) )-1]被覆盖。
最后就是简单计数。
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48638209&returnHomeType=1&uid=467843024
写在最后：感觉没能彻底理解，锁了。
查看4道真题和解析