题解：P12355 「HCOI-R2」巡回演出

· · 题解

一个来自 hyman00 的组合意义做法，这篇题解是他写的。

记 C_n 为卡特兰数的第 n 项。

首先答案和节点编号无关，可以重编号为 1,2,\dots,n，直接忽略 s 序列。

另外只关心一个节点的经过次数，把 w 序列做前缀和 h_i=\sum_{j=1}^i w_j，经过 i 次的贡献就是 h_i。对一棵树算答案，容易发现非根节点经过的次数是它的儿子数 +1，根节点的经过次数是它的儿子数。分别计算不是根和是根的贡献。

树可以转括号序列：在 dfs 过程中向下走加入左括号，向上走加入右括号。合法的树和长度为 2n-2 的括号序列一一对应，因此合法的树的个数即为 C_{n-1}，可以通过 B 性质。

考虑计算一个非根点的贡献。枚举这个点有 x 个儿子，即序列里有 ((...)(...)...(...)) 这样的关系（这个点对应的括号内有 x 段合法的括号序列），再枚举子树内有 y 个节点，即这段的总长度是 2y。

内部的方案数为：

\sum_{s_1+\dots+s_k=y-1}\prod_{i=1}^k C_{s_i-1}

这是经典的卡特兰卷积，它的组合意义是在二维网格上每次向右上或右下走一格，不经过 y<-(x-1) 的位置，从 (0,0) 走到 (2y-2-2x+(x-1),-(x-1))=(2y-x-3,-x+1) 的路径的数量。对应关系可以看作把路径上 y 坐标第一次变成 -1,-2,\dots,-(x-1) 的移动当作分隔符，分成 x 段，每段外面套上一对括号。这个先不急着写成组合数。

然后考虑节点外面的方案数，外面还剩 n-1-y 对括号，且这个序列可以插入的位置有 2(n-1-y)+1 个，因此是：

(2(n-1-y)+1)C_{n-1-y}=\frac{(2n-1-2y)(2n-2-2y)!}{(n-1-y)!(n-y)!}=\binom{2n-1-2y}{n-y}

这也是组合数。在前面的路径末尾加一个分隔符，拼起来，就是在二维网格上从 (0,0) 走到 (2n-x-3,-x-1) 的路径的数量。这里根据分隔符的位置包含了所有 y 的情况，直接算出了所有 y 的和，因此不用枚举 y，贡献为 h_{x+1}\binom{2n-x-3}{n-1}。

非根节点的贡献和即为 \sum_{x=1}^{n}h_x\binom{2n-x-2}{n-1}。

考虑根节点，还是一样枚举 x，这里可以认为 y=n，只用考虑里面的方案。贡献和为 \sum_{x=1}^{n}h_x\left(\binom{2n-x-3}{n-2}-\binom{2n-x-3}{n-1}\right)，把这两部分加起来就是答案。

因此答案为：

\sum_{x=1}^{n}h_x\left(\binom{2n-x-2}{n-1}+\binom{2n-x-3}{n-2}-\binom{2n-x-3}{n-1}\right)=2\sum_{x}h_x\binom{2n-x-3}{n-2}

直接计算即可。