Rikka with Intersections of Paths ICPC 2018 Xuzhou R

[ICPC 2018 Xuzhou R] Rikka with Intersections of Paths

题目链接： [ICPC 2018 Xuzhou R] Rikka with Intersections of Paths 。

题目描述：

有 $n$ 个点的树， $m$ 条路径，求选出 $k$ 个路径满足有至少一个公共点的方案数，对 $10^9+7$ 取模。

$n,m,k\le 3\times 10^5$ 。

一眼树上差分统计每一个点被多少路径覆盖。记为 $cnt_i$ 。

然而直接计算 $\sum \binom{cnt_i}{k}$ 有问题，因为可能有些路径拥有超过 $1$ 个公共点，这些路径就会在他们的所有公共点处被重复统计。

注意到以下性质：

一个路径 $x,y$ 经过 $i$ 意味着 $lca(x,y)$ 为 $i$ 的祖先或 $i$ 。

也就是说，所有经过 $i$ 的路径的 $lca$ 必然为 $i$ 的祖先或 $i$ 。于是一个基本的容斥想法形成：

我们可以对于每一个 $i$ ，统计“至少有一个路径的 $lca$ 为 $i$ 的选 $k$ 条经过 $i$ 的路径的方案数”，这样算是不重复不遗漏的，因为每一种方案一定仅会在他们的所有 $lca$ 中深度最大处被统计。

具体来说就是设 $cnt2_i$ 表示 $i$ 为多少路径的 $lca$ 。则答案可以表示为 $\sum \binom{cnt_i}{k}-\binom{cnt_i-cnt2_i}{k}$ 。

代码不放了。