[集训队互测2022]Path 题解

考虑对于两条路径\(I_i,I_j\)计算可以产生贡献的\(I\)的数量。

分类讨论:

1.\(I_i,I_j\)端点不相交

可以发现\(I_i\subseteq I,I_j\subseteq I\)。

对于任意一条路径 \(I_i\) ，符合条件的\(I\)的起点和终点都是一段区间，贡献也是二维数点的形式，可以离线扫描线解决。

2.\(I_i,I_j\)端点相交

因为保证\(I_i\neq I_j\)，所以两条路径只有一个端点相同.

枚举相同的断点，对于所有以这个点位端点的路径的另一个端点建虚树，然后树形dp考虑贡献。

对于\(I_i,I_j\subseteq I\)的贡献上边可以一块计算，因此可以得出符合条件的\(I,I_i,I_j\)必定在\(root\)的同一棵子树中。

设\(r(I)\)是路径\(I\)非\(root\)的端点。

<1>.若\(r(I_i)\)和\(r(I_j)\)分属不同的子树。

可以发现贡献为\(siz_{r_(I_i)}siz_{r(I_j)}\)，记\(f_x=\sum_{r(I_j)\subseteq subtree(x)}siz_{r(I_j)}\)

背包合并即可。

<2> 否则就说明\(I_j\)是\(I_i\)的子树中的点

:1 \(r(I_j)\in son(r(I_i))\)

此时答案为所有跨过\(r(I_j)\)的路径条数。

:2

贡献为在该儿子子树内选择一个路径端点的子树中的点的方案乘上在外边选择的方案。

都可以树形dp计算。