考虑当m=0时，任何点均为0，那么两问的答案均为0。

考虑当n=1时，只有一个点，那么两问的答案是一样的，均为(2^m-1)/2。

接下来进入正解部分，考虑拆位对于每一个叶子算贡献。

叶子节点到根节点路径上有n个节点，那么要是想要这条路径上的这一位的AND值为1，就需要每个节点这一位都是1，概率为(1/2)^n，想要这条路径上的这一位的XOR值为1，就需要每个节点有奇数个节点为是1，概率为1/2。

最终有2^(n-1)个叶子节点，总共有m位2^m-1个贡献，总答案相乘即可。

Tags:math,probabilities,trees Difficulty:1700