\(\text{「ABC222H」Beautiful Binary Tree}\)
\(\text{Link}\)
\(\text{Describe}\)
对于一个正整数 \(n\)，我们称满足以下条件的有根二叉树是一棵美丽的 \(n\) 阶二叉树。
- 每个节点有一个数字 \(0\) 或 \(1\)，节点 \(i\) 的数字记为 \(a_i\)。
- 每个叶子节点的数字定是 \(1\)。
- 可以通过进行如下的操作至多 \(n - 1\) 次，使得最终根节点上的数字为 \(n\)，其余节点的数字是 \(0\)。
- 选择两个节点 \(u, v\)，其中 \(u\) 需要是 \(v\) 的父节点或父节点的父节点。作赋值 \(a_u\leftarrow a_u + a_v, a_v\leftarrow 0\)。
给定 \(n\)，请计算美丽的 \(n\) 阶二叉树的数量。答案对 \(998244353\) 取模。
\(\text{Solution}\)
容易发现美丽的 \(n\) 阶二叉树的等价限制为
-
每个叶子节点的数字是 \(1\)；
-
根的数字为 \(1\)；
-
\(\forall (u,v)\in E,a_u=1\vee a_v=1\)；
考虑定义根的数字为 \(0/1\) 的 \(\text{GF}\) 记为 \(F/G\)，容易构造出 \(F,G\) 的关系
\[\begin{aligned} &F(x)=x(F(x)+G(x))^2+1\\ &G(x)=F^2(x)-1 \end{aligned} \]转化为
\[F(x)=x(F^2(x)+F(x)-1)^2+1 \]考虑用拉格朗日反演提取系数，因为右边的常数项无法与 \(x^k\) 消掉，考虑换元 \(H(x)=F(x)-1\)，有
\[\dfrac{H(x)}{(H^2(x)+3H(x)+1)^2}=x \]其复合逆为 \(R(x)=\dfrac{x}{x^2+3x+1}\).
运用拉格朗日反演容易有
\[[x^n]H(x)=\dfrac{1}{n}[x^{n-1}](x^2+3x+1)^n \]容易 \(O(n)\) 直接计算。
\(\text{「CF566C」Logistical Questions}\)
\(\text{Link}\)
\(\text{Describe}\)
一棵 \(n\) 个节点的树，点有点权，边有边权。
两点间的距离定义为两点间边权和的 \(\frac 32\) 次方。
求这棵树的带权重心。