官方题解只能做到 $O(n^2)$？玩的太差了。可以先把最坏时间复杂度降到 **$O(n^{5/3}\log^2 n)$，再降到 $O(n^{3/2} \log^{3/2} n)$。
关键是树分块，并用带重数的多点求值，批量处理一个块两侧的大子树。
$O(n^{5/3}\log^2 n)$ 算法
1. 保留计数公式，改变计算方式
先简要说明计数基础。对于每个原树叶子 $a$，令 $R_a$ 为从 $a$ 不换乘可以到达的点集，其中包含 $a$ 自身。它是树上的连通子树。任意两点至多乘坐两条线路，等价于这些 $R_a$ 存在公共交点。
必要性来自树上连通子树的 Helly 性质：两两相交就有公共交点。充分性也很直接：若所有叶子都能直达 $x$，对于任意点 $u$，选取一个使叶子到 $x$ 的路径经过 $u$ 的叶子，那么 $u$ 也能直达 $x$。
公共交集非空时，它是一棵树，点数减边数等于 $1$。因此可以枚举公共交集包含的点，再减去它包含的边。这也是公开题解采用的基本观察。([QOJ][1])
记原树有 $L$ 个叶子，$N=\binom n2$。把每条可能的线路以概率 $1/2$ 独立选择，最后将所得概率乘上 $2^N$。
定义 $F_{s,b}(z)=\sum_{k=0}^b(-1)^k\binom bk2^{sk-\binom k2}z^k$，以及 $w_k=2^{-nk+\binom k2}$。这里，$s,b$ 分别表示某个连通块的点数和原树叶子数。
如果删除一个非叶子 $u$ 后，各连通块对应的多项式乘积为 $P(z)$，那么 $u$ 属于公共交集的概率为 $\sum_k[z^k]P(z)w_k$。这是因为容斥选出若干个不能直达 $u$ 的叶子后，不同连通块中的两个被选叶子之间的线路被重复禁选了一次，而因子 $2^{\binom k2}$ 恰好处理这些交叉项。
选择一个非叶子作为根。记 $s_u,b_u$ 为子树大小、子树叶子数，并定义 $H_u=\prod_{v\text{ 是 }u\text{ 的儿子}}F_{s_v,b_v}-F_{s_u,b_u}$；根的定义中不减去最后一项。
上一版已经得到：点 $u$ 的贡献减去父边的贡献，等于
$$ G_u=\sum_{k=0}^{b_u}[z^k]H_u(z)\,w_k \left(1-2^{k-s_u}\right)^{L-b_u}. $$
根没有父边，直接计算点贡献。答案为 $2^N\sum_uG_u$。非根叶子的 $G_u=0$，可以跳过。
这个公式本身没有问题，但不能对每个大子树都完整展开。下面只对少量点直接使用它。
2. 把树分成至多有两个边界的小块
取分块参数 $B$，最终设为 $\lceil n^{1/3}\rceil$。
从下往上处理树，维护尚未被标记点隔开的连通部分。当这个部分的点数达到 $B$，或者它已经连接到至少两个下方的标记点时，就将当前点标记。根也标记。
由此得到两个性质。
首先，标记点只有 $O(n/B)$ 个。因大小达到 $B$ 而产生的标记点，可以各自收取至少 $B$ 个互不重复的点；其余非根标记点在标记点组成的骨架中至少有两个儿子，这类分叉点的数量也是 $O(n/B)$。
其次，删除标记点后，每个连通块大小小于 $B$，并且至多连接两个标记点：上方一个，下方至多一个。
对于标记点，直接用上述单点公式。生成所有儿子多项式并用平衡乘积树合并，需要 $O(n\log^2 n)$ 时间，所以这些点的总复杂度是 $O((n^2/B)\log^2 n)$。
只连接一个边界的块，其中各点的子树都很小，直接计算即可。对于连接两个边界的块，考虑连接两边界的那条路径，称为块的主链。主链之外的点也都拥有大小小于 $B$ 的子树，仍然直接计算。
真正需要批处理的，仅仅是双边界块的主链。 双边界块至多有 $O(n/B)$ 个。
考虑一个大小为 $c< B$ 的双边界块。将块外分成上、下两部分，其点数分别为 $a,b$，叶子数分别为 $\alpha,\beta$。于是 $a+b+c=n$，块内叶子数为 $\gamma=L-\alpha-\beta\le c$。
为整个块定义同一张表：
$$ K_{x,y}= \sum_{i=0}^{\beta}\sum_{j=0}^{\alpha} (-1)^{i+j}\binom{\beta}{i}\binom{\alpha}{j} 2^{(b-n+x)i+(a-n+y)j+ij}, \qquad 0\le x,y\le c. $$
其中 $i,j$ 分别是下方、上方块外叶子的容斥数量。这张表一旦算出，主链上所有点和边的贡献都可以仅用块内状态计算。
具体地，删除主链上的点 $u$ 后，设上方连通块有 $a+d_A$ 个点、$\alpha+U$ 个叶子，下方连通块有 $b+d_B$ 个点、$\beta+V$ 个叶子。其余小分支都在块内，令它们的多项式乘积为 $Q(z)=\sum_rg_rz^r$。
枚举上方、下方、侧分支中分别选了 $p,q,r$ 个块内叶子。它们与下方块外叶子的交叉项有 $p+r$ 个，与上方块外叶子的交叉项有 $q+r$ 个，所以点贡献为
$$ A_u= \sum_{p,q,r} [z^p]F_{a+d_A,U}\, [z^q]F_{b+d_B,V}\, g_r\,w_{p+q+r}\, K_{d_B+p+r,\ d_A+q+r}. $$
父边贡献完全相同，只是没有侧分支，直接使用边两侧的大小和叶子数，再将其减去。
这些下标不会超过 $c$：例如 $d_B$ 统计下方连通块中的块内点，而 $p+r$ 统计不在该连通块中的被选块内叶子，它们对应互不重复的块内点。
这里看起来每个点要枚举三个变量，但一个块的总开销只有 $O(c^3)$，不是 $O(c^4)$。设某主链点的侧分支叶子数为 $R_u$，则该点的枚举量至多为 $(c+1)^2(R_u+1)$；不同主链点的侧分支互不相交，所以 $\sum_uR_u\le c$。所有点贡献以及边贡献加起来都是 $O(c^3)$。
剩下的问题是：怎样避免花 $O(nc^2)$ 时间计算整张 $K$？
3. 用带重数的多点求值计算整张表
先对 $j$ 使用二项式定理。令 $z_x=-2^{b-n+x}$、$Y=2^{a-n}$，则 $K_{x,y}=\sum_{i=0}^{\beta}\binom{\beta}{i}z_x^i(1-Y2^{i+y})^\alpha$。
将求和下标平移为 $t=i+y$，并构造多项式
$$ D(z)= \sum_{t=0}^{\beta+c} \frac{(1-Y2^t)^\alpha}{t!(\beta+c-t)!}\,z^t. $$
它的次数至多为 $n$，系数可以在 $O(n\log n)$ 时间内生成。
对每个 $x=0,\ldots,c$，求出 $D$ 在 $z_x$ 处的前 $c+1$ 个 Taylor 系数 $J_{x,r}=[h^r]D(z_x+h)$。接着定义 $T_x(v)=\sum_{r=0}^cJ_{x,r}z_x^r\frac{(\beta+c-r)!}{(c-r)!}v^r$，就有
$$ \boxed{ K_{x,y} = y!(c-y)!\,z_x^{-y}\,[v^y]T_x(v-1) }. $$
下面说明这个变换为什么成立。记下降阶乘为 $(t)*{\underline r}$，则 $\binom{\beta}{t-y}=\frac{\beta!}{t!(\beta+c-t)!}(t)*{\underline y}(\beta+c-t)_{\underline{c-y}}$。取值不合法时，右边的下降阶乘自动为零。
再使用恒等式 $\sum_y\binom cy(t)*{\underline y}(\beta+c-t)*{\underline{c-y}}v^y=c^t(1+h)^{\beta+c-t}$，代入 $D$，并将 $D\bigl(z_x(1+vh)/(1+h)\bigr)$ 在 $z_x$ 处展开，就得到上述公式。于是一次 Taylor 系数求值加一次多项式平移，便能得到一整行 $K_{x,0},\ldots,K_{x,c}$。
现在需要在 $c+1$ 个点处，各求前 $c+1$ 个 Taylor 系数。建立多项式乘积树，第 $x$ 个叶子的多项式是 $(z-z_x)^{c+1}$，再将 $D$ 沿乘积树向下取余。
到达叶子时，余式与 $D$ 在 $z_x$ 处的前 $c+1$ 个 Taylor 系数完全相同。余式次数仅为 $c$，将它平移到 $z_x$ 即可。多项式平移通过阶乘卷积实现，代码中包含完整实现。
整棵乘积树的总次数是 $(c+1)^2$，因此计算整张表的复杂度为 $O(n\log n+c^2\log^2 c)$。加上块内枚举，每个双边界块的复杂度为 $O(n\log n+c^2\log^2 c+c^3)$。
4. 总复杂度与完整实现
标记点的总开销为 $O((n^2/B)\log^2n)$。双边界块有 $O(n/B)$ 个，且各块互不相交、大小小于 $B$，因此它们的局部枚举满足 $\sum c^3\le nB^2$。小子树的直接计算也包含在较低阶开销中。
所以，当 $B=\Theta(n^{1/3})$ 时，总时间复杂度为 $O(n^{5/3}\log^2n)=o(n^2)$。
各个块依次处理。一个块的多点求值乘积树占用 $O(B^2\log B)$ 空间，其余临时多项式占用 $O(n)$ 空间；代入 $B=\Theta(n^{1/3})$，总额外空间为 $O(n)$。
提交记录：https://qoj.ac/submission/2952086 。
$O(n^{3/2} \log^{3/2} n)$ 算法
可以进一步做到 $O(n^{3/2}\log^{3/2}n)$ 时间、$O(n)$ 额外空间，即 $\widetilde O(n^{3/2})$。
这次的核心改进是：不再逐点计算双边界块的贡献，而是先进行统一的系数缩放，把整条主链的贡献合成为一个二元多项式。 这样，大小为 $c$ 的块，其内部计算从上一版的 $O(c^3)$ 降到 $O(c^2\log c)$。再单独处理最大的子树多项式，还能省掉总体复杂度中的半个对数因子。
下面给出推导和完整实现。这个上界严格优于上一版，但还没有证明它就是这道题的最优复杂度。
计数公式与分块
先保留之前的计数基础。对每个原树叶子 $a$，令 $R_a$ 为从 $a$ 不换乘可以到达的点集，包含 $a$ 自身。它是树上的连通子树。
合法方案要求这些子树两两相交，而树上的连通子树两两相交必有公共交点。反过来，若公共交点为 $x$，任意点都位于某条叶子到 $x$ 的路径上，因此任意点也都能直达 $x$。所以，合法等价于 $\bigcap_aR_a$ 非空。公共交集非空时是一棵树，可以用“点数减边数”等于 $1$ 计数。这也是公开题解采用的基本观察。([QOJ][1])
设原树有 $L$ 个叶子，将每条可能的线路以概率 $1/2$ 独立选择，最后乘上 $2^{\binom n2}$。
定义 $F_{s,b}(z)=\sum_{k=0}^b(-1)^k\binom bk2^{sk-\binom k2}z^k$，以及 $w_k=2^{-nk+\binom k2}$。选择非叶子作为根，记 $s_u,b_u$ 为子树大小和子树叶子数。
对非根点定义 $H_u(z)=\prod_{v\text{ 是 }u\text{ 的儿子}}F_{s_v,b_v}(z)-F_{s_u,b_u}(z)$，根的定义中不减去最后一项。容斥后，点 $u$ 减去父边的贡献为 $G_u=\sum_k[z^k]H_u(z),w_k(1-2^{k-s_u})^{L-b_u}$，答案就是 $2^{\binom n2}\sum_uG_u$。
这里对子树外叶子的容斥已经用二项式定理消去了。非根叶子的 $G_u=0$，不需要计算；$n\le2$ 时答案为 $1$。
仍然使用双边界分块，参数记为 $B$。从下往上维护尚未被标记点隔开的连通部分；当它的大小达到 $B$，或者连接了至少两个下方标记点，就标记当前点。根也标记。
这样，标记点有 $O(n/B)$ 个。由大小触发的标记点，各自可以收取至少 $B$ 个不重复的点；其余标记点是标记点骨架中的分叉点，数量也是 $O(n/B)$。删除标记点后，每个块大小小于 $B$，至多有上下两个边界。
标记点直接用 $G_u$ 计算。单边界块中的点，以及双边界块主链之外的点，其子树大小都小于 $B$，也直接计算。需要批处理的仅是双边界块的主链。
关键优化：把整条主链的贡献合并
考虑一个大小为 $c< B$ 的双边界块。块外上、下两部分的点数分别为 $a,b$，叶子数分别为 $\alpha,\beta$，满足 $a+b+c=n$。
沿主链从上往下排列节点。对主链节点 $u_i$，令 $h_i$ 为它自身加上所有侧分支的点数，$\ell_i$ 为这些侧分支的叶子数。于是 $\sum_i h_i=c$，且 $\ell_i< h_i$。
令 $d_i=\sum_{j< i}h_j$、$e_i=\sum_{j>i}h_j$，分别表示它上方、下方的块内点数；对应的块内叶子数记为 $U_i=\sum_{j< i}\ell_j$、$V_i=\sum_{j>i}\ell_j$。它的侧分支多项式乘积记为 $Q_i(z)=\sum_rg_{i,r}z^r$。
整个块共用一张外部系数表：
$K_{x,y}=\sum_{p=0}^{\beta}\sum_{q=0}^{\alpha}(-1)^{p+q}\binom{\beta}{p}\binom{\alpha}{q}2^{(b-n+x)p+(a-n+y)q+pq}$，其中 $0\le x,y\le c$。
上一版的问题在于，对每个主链点，都要枚举上方、下方、侧分支中被选中的块内叶子数量。若这三个数量为 $p,q,r$，对应项为 $[z^p]F_{a+d_i,U_i},[z^q]F_{b+e_i,V_i},g_{i,r}w_{p+q+r}K_{e_i+p+r,d_i+q+r}$。逐点计算导致一个块需要 $O(c^3)$ 时间。
现在引入统一缩放 $W_{x,y}=2^{(a-n)x+(b-n)y+xy}$，并记 $C(d,e)=W_{e,d}^{-1}=2^{(n-a)e+(n-b)d-de}$。
展开指数，利用 $a+b+d_i+e_i+h_i=n$，得到最关键的等式：
$$ \frac{ [z^p]F_{a+d_i,U_i}\, [z^q]F_{b+e_i,V_i}\, g_{i,r}w_{p+q+r} }{ W_{e_i+p+r,d_i+q+r} } = C(d_i,e_i)(-1)^{p+q} \binom{U_i}{p}\binom{V_i}{q} g_{i,r}\,2^{(h_i-1)r-\binom r2}. $$
原先耦合 $p,q,r$ 的交叉项，被统一的 $W$ 吸收了。剩下的三个部分可以直接相乘。
定义 $D_i(T)=\sum_rg_{i,r}2^{(h_i-1)r-\binom r2}T^r$。缩放之后，点 $u_i$ 的贡献多项式为 $C(d_i,e_i)X^{e_i}Y^{d_i}(1-X)^{U_i}(1-Y)^{V_i}D_i(XY)$。
它的父边对应的多项式则为 $C(d_i,e_i+h_i)X^{e_i+h_i}Y^{d_i}(1-X)^{U_i}(1-Y)^{V_i+\ell_i}$。
进一步定义 $L_i(X,Y)=Y^{h_i}(1-X)^{\ell_i}$、$R_i(X,Y)=X^{h_i}(1-Y)^{\ell_i}$，以及单点多项式 $S_i(X,Y)=C(d_i,e_i)D_i(XY)-C(d_i,e_i+h_i)R_i(X,Y)$。
那么整条主链的贡献多项式就是 $P=\sum_i\bigl(\prod_{j< i}L_j\bigr)S_i\bigl(\prod_{j>i}R_j\bigr)$。得到 $P$ 后，整个块的贡献只需计算 $\sum_{x,y}[X^xY^y]P\cdot W_{x,y}K_{x,y}$。
这个前缀、后缀乘积之和可以分治合并。
对于相邻区间 $I,J$，记它们的点数之和分别为 $h_I,h_J$，叶子数之和分别为 $\ell_I,\ell_J$。合并公式为：
$$ \boxed{ P_{I\cup J} = P_I\cdot X^{h_J}(1-Y)^{\ell_J} + Y^{h_I}(1-X)^{\ell_I}\cdot P_J. } $$
这不需要一般的二元多项式乘法：第一项只需对每一行乘一个一元多项式，再平移 $X$ 次数；第二项只需对每一列乘一个一元多项式，再平移 $Y$ 次数。
一个包含 $h$ 个点的区间，每个变量的次数都不超过 $h$，所以存储 $O(h^2)$ 个系数即可。一轮合并使用逐行、逐列 NTT，复杂度为 $O(h^2\log h)$。
分治时按点数权重 $h_i$ 选择中位节点，使两侧递归区间的点数都不超过当前区间的一半。因此，一个块的全部合并开销为 $O(c^2\log c)$，不再是 $O(c^3)$。
外部系数表与完整复杂度
还需要快速计算 $K$。这一部分沿用上一版的带重数多点求值，但利用求值点的等比结构，将空间保持在线性。
令 $z_x=-2^{b-n+x}$、$Y=2^{a-n}$。先对外部上方叶子的容斥使用二项式定理，得到 $K_{x,y}=\sum_{i=0}^{\beta}\binom{\beta}{i}z_x^i(1-Y2^{i+y})^\alpha$。
构造次数不超过 $n$ 的多项式 $D(z)=\sum_{t=0}^{\beta+c}\frac{(1-Y2^t)^\alpha}{t!(\beta+c-t)!}z^t$，并求出它在每个 $z_x$ 处的前 $c+1$ 个 Taylor 系数 $J_{x,r}=[h^r]D(z_x+h)$。
定义 $T_x(v)=\sum_{r=0}^cJ_{x,r}z_x^r\frac{(\beta+c-r)!}{(c-r)!}v^r$，则有：
$$ \boxed{ K_{x,y} = y!(c-y)!\,z_x^{-y}\,[v^y]T_x(v-1). } $$
这个变换可以直接由下降阶乘恒等式验证。令 $d=\beta+c$，将 $t=i+y$ 代入，并使用 $\binom{\beta}{t-y}=\frac{\beta!,(t)*{\underline y}(d-t)*{\underline{c-y}}}{t!(d-t)!}$；再通过 $(1+vh)^t(1+h)^{d-t}$ 提取 $h^c$ 的系数，按 Taylor 展开的阶数整理，就得到上式。
因此，每个求值点只需要一次多项式平移，就能恢复一整行 $K$。
求 Taylor 系数时，对每个点使用模数多项式 $(z-z_x)^{c+1}$，沿乘积树向下取余。全部模数的总次数为 $O(c^2)$，所以整张表可以在 $O(n\log n+c^2\log^2c)$ 时间内计算。
普通乘积树会占用 $O(c^2\log c)$ 空间，但这里 $z_x=z_0,2^x$。长度相同的任意区间，其模数多项式都只是同一个多项式的根整体乘上 $2^l$。因此，每种二次幂长度只存一个模板，就能在递归时恢复需要的模数。所有模板的次数之和是 $O(c^2)$，深度优先取余的空间也是 $O(n+c^2)$。
最后还要避免直接计算标记点时，大多项式在乘积树中反复参与卷积。
对每个点，把叶子数最多的儿子单独拿出来；先求其他儿子的多项式乘积，再与这个最大多项式只合并一次。设其他儿子的叶子数之和为 $t_u$，求它们的乘积需要 $O(t_u\log^2n)$ 时间，而全树满足 $\sum_ut_u=O(n\log n)$：每次一个叶子进入非最大儿子，对应子树叶子数至少减半。
因此，这部分额外乘积开销总计为 $O(n\log^3n)$。标记点与小子树的系数扫描、快速幂和最后一次合并，总开销为 $O((n^2/B+nB)\log n)$。
双边界块有 $O(n/B)$ 个，且 $\sum c^2\le nB$。合并所有开销，得到：
$$ T(n,B)= O\!\left( \frac{n^2}{B}\log n +nB\log^2n +n\log^3n \right). $$
取 $B=\Theta(\sqrt{n/\log n})$，得到 $O(n^{3/2}\log^{3/2}n)$；其中 $n\log^3n$ 是更低阶项。各个块依次处理，空间为 $O(n+B^2)=O(n)$。