题解

思路推导

先考虑 $k\ge2$。若一组路径合法，则被全部 $k$ 条路径包含的边在树上连成一条非空简单路径，称为公共核心。公共核心之外的边不能被两条或更多但不足 $k$ 条路径包含，因此每条这样的边至多属于一条所选路径。

固定公共核心的两个端点 $u,v$。每条路径都由三部分组成：从某个端点延伸到 $u$ 的一段、公共核心 $u\leadsto v$、以及从 $v$ 延伸到另一个端点的一段。在 $u$ 一侧，两条不同的路径不能进入同一条离开 $u$ 的支路，否则该支路的第一条边会至少被使用两次。$v$ 一侧同理。

删除顶点 $u$ 后，设某条相邻支路所在连通块的大小为 $s$。若核心从 $u$ 经相邻点 $w$ 离开，则不能把这条支路当作核心外延伸。对其余支路，选择 $t$ 条互不相同的支路、在每条支路中选择一个端点，并把 $t$ 个互不相同的路径编号分配给它们。令这些支路大小的第 $t$ 个初等对称和为 $e_t$，方案数为

$$H(u,w)=\sum_{t=0}^{\min(k,\deg(u)-1)}(k)_t e_t,$$

其中 $(k)_t=k(k-1)\cdots(k-t+1)$。因此固定核心 $u\leadsto v$ 的方案数为

$$H(u,\operatorname{next}_u(v))\,H(v,\operatorname{next}_v(u)).$$

当 $k\ge2$ 时，核心外每条支路至多分配给一个路径编号，所以公共核心自动是全部路径交集的最大部分，每个合法方案恰好被统计一次。$k=1$ 时单独处理，答案就是树上非空简单路径数 $n(n-1)/2$。

做法

子任务 1：枚举有序路径组

枚举树上全部 $n(n-1)/2$ 条非空简单路径，再枚举长度为 $k$ 的有序路径组。统计每条边出现次数并直接检查其是否属于集合 $\{0,1,k\}$，以及是否存在次数为 $k$ 的边。

子任务 2：直接计算初等对称和

对每个顶点逐条加入相邻支路，用背包式递推求出初等对称和。再对每一种被排除的支路大小做一次合成除法，即可得到所有 $H(u,w)$。在 $n\le2000$ 时，直接执行这些二次转移即可。

满分算法：NTT 与支路大小去重

对顶点 $u$ 的所有相邻支路大小 $s_1,s_2,\ldots,s_d$，建立多项式

$$P_u(x)=\prod_{i=1}^{d}(1+s_i x)=\sum_{j=0}^{d}p_jx^j.$$

使用分治 NTT 构造 $P_u$，并只保留不超过 $k$ 次的系数。若要排除大小为 $s$ 的一条支路，设

$$Q(x)=\frac{P_u(x)}{1+sx}=\sum q_jx^j,$$

则有 $q_0=1$ 以及

$$q_j=p_j-sq_{j-1}.$$

于是一次线性扫描即可得到对应的 $H(u,w)$。同一顶点处，支路大小相同的方向具有相同答案，只需计算一次。所有支路大小都是正整数且总和为 $n-1$，若有 $r$ 种不同大小，则

$$1+2+\cdots+r\le n-1,$$

所以 $r=O(\sqrt n)$。全部顶点的合成除法总量因此为 $O(n\sqrt n)$。

最后需要对所有可能的公共核心求和。任意给树定根，令 $M(u\to p)$ 表示以 $u$ 所在子树中的某个顶点作为核心端点、核心继续经过父亲 $p$ 时，该端点贡献之和，则

$$M(u\to p)=H(u,p)+\sum_{x\text{ 是 }u\text{ 的儿子}}M(x\to u).$$

在顶点 $u$ 处：

• 一个核心端点正好是 $u$、另一个位于儿子 $x$ 的子树时，贡献为 $H(u,x)M(x\to u)$；
• 两个端点分别位于不同儿子子树时，贡献为两个对应 $M$ 的乘积。

按最近公共祖先分类累加上述两类贡献，每对不同核心端点恰好出现一次。

正确性证明

引理 1

当 $k\ge2$ 时，任意合法路径组的公共边构成一条非空简单路径，且公共核心之外的每条边至多被一条所选路径包含。

证明。 树上若两条边同时属于一条简单路径，则它们之间的整段路径也属于该路径。因此全部路径的边交集连通，且题目要求它非空，所以它是一条非空简单路径。题目只允许边的出现次数为 $0$、$1$ 或 $k$；不在交集中的边次数不为 $k$，故至多为 $1$。$\square$

引理 2

固定核心在端点 $u$ 处离开的方向 $w$ 后，核心左侧延伸方案数等于 $H(u,w)$。

证明。 核心外一条支路至多被一条路径使用，因此需要选择若干互不相同的支路。选择 $t$ 条支路并在每条中选一个端点的加权和正是 $e_t$；再从 $k$ 个有标号路径中依次分配 $t$ 个不同编号，共有 $(k)_t$ 种。对所有合法 $t$ 求和得到公式，且每个延伸方案对应唯一的支路、端点和编号选择。$\square$

引理 3

固定公共核心 $u\leadsto v$ 的合法路径组数为两个端点贡献的乘积。

证明。 每个路径编号可以在核心两端独立选择是否延伸以及延伸到哪个支路端点。由引理 1，同一侧不同编号使用的支路互不相同；两端位于核心的不同侧，不会共享核心外边。故两侧选择相互独立，方案数相乘。$\square$

引理 4

树形求和过程将每一条非空核心路径恰好统计一次。

证明。 对核心两个端点取最近公共祖先。若其中一个端点就是该祖先，它属于第一类贡献；否则两个端点位于两个不同儿子子树，属于第二类贡献。两种情况互斥，且在其他顶点处不会满足相同的最近公共祖先分类。每项乘积中的方向权值由引理 2、3 给出。$\square$

定理

算法输出满足题目条件的有序路径组数量。

证明。 $k=1$ 的结论直接来自每条非空简单路径都是唯一所选路径。对 $k\ge2$，引理 1 给出每个合法方案的唯一公共核心；引理 2、3 精确计算固定核心的方案数；引理 4 对全部核心不重不漏地求和。因此最终结果正确。$\square$

复杂度分析

所有顶点的多项式乘积总时间为 $O(n\log^2 n)$，所有不同支路大小的合成除法总时间为 $O(n\sqrt n)$，树形求和为 $O(n)$。总时间复杂度为 $O(n\log^2 n+n\sqrt n)$，空间复杂度为 $O(n)$。