FST王者

题解路径计数机题解

题解

/ 注册

路径计数机题解

669 浏览 0 回复 2019-11-08

FST王者

+关注

路径计数机

https://ac.nowcoder.com/acm/contest/1103/B

$有一棵n个点的树和两个整数p, q，求满足以下条件的四元组(a, b, c, d)的个数：$
$1.1≤a, b, c, d≤n。$
$2.点a到点b的经过的边数为p。$
$3.点c到点d的经过的边数为q。$
$4.不存在一个点，它既在点a到点b的路径上，又在点c到点d的路径上。$

注意到不相交的情况太多(我考场上写换根写疯了)

首先考虑反求问题，不相交的路径数=所有路径数-相交路径数

考虑相交有哪些情况

我们把第三种颜色互换一下就变成了第二种

我们发现绿色的链总是过黑链的 $lca$ 的

我们考虑枚举这个 $lca$

他可以是两条只在子树内的链或者是一条子树内的链和一条从子树内(可以不进)到子树外的链

因此我们只需要算过一个点 $x$ 子树内的链长为 $p/q$ 方案数 $f_{x,p/q}$ 以及从子树内(可以不进)到子树外的链长为 $p/q$ 方案数 $g_{x,p/q}$

考虑一条链拆成两条

设从 $x$ 出发,子数内单链长为 $k$ 的方案 $sf_{x,k}$

则 $\displaystyle{sf_{x,k}=\sum_{y\in son_x}}sf_{y,k-1}$

设从 $x$ 出发,子数外单链长为 $k$ 的方案 $gf_{x,k}$

则 $\displaystyle{sg_{x,k}=sg_{fa_x,k-1}+sf_{fa_x,k-1}-sf_{x,k-2}}$

就是来自父亲上面的，父亲下面不过自己的

合并的时候是类似背包的,我们把前面的儿子( $sf'$ )与 $y(sf)$ 合并

因此 $\displaystyle{f_{x,p/q}=\sum_{k\in[0,p/q)}sf'_{x,k}\times sf_{x,p/q-k-1}}$

$g$ 更简单

$\displaystyle{g_{x,p/q}=\sum_{k\in[0,p/q]}sf_{x,k}\times sg_{x,p/q-k}}$

举报

收藏

赞 3

评论加载中...