下面是我的思路，求助是哪里贡献没有统计

所有贡献分成两部分来算：

• 直上直下
• 一条折的路径

对于第一部分，可以先计算有多少子树深度 $\ge k$，然后每棵子树的贡献为 $2^k$，总贡献为 $(2^{n-k} - 1) \times 2^k \times 2$（因为是点对还要 $\times 2$）。

对于第二部分，将 $k$ 拆成两条直上直下的路径，设 $k = x + y \ (x > y)$。然后枚举所有 $x$。同样先计算有多少子树深度 $\ge x$，然后每棵子树的贡献为 $2^{x-1} \times 2^{y-1} \times 2$（这棵子树的左子树路径条数 $\times$ 右子树路径条数 $\times 2$），而合法的子树有 $2^{n-x}-1$ 棵。

对所有贡献求和。

几个小数据是对的，但是大数据没过。