P4630 [APIO2018] 铁人两项 题解

今天学习了圆方树，并且做了一道和这道题很像的题，于是就又来做了一下这道题。

题意

给定一张不保证连通的无向图。求有多少个点对 \((a,b,c)\) 满足 \(a\) 到 \(c\) 的简单路径上经过了点 \(b\)。

思路

显然圆方树。点双缩点过后构造一颗圆方树，然后考虑如何计算答案。圆方树有一个实用的技巧：在路径统计的时候，将圆点和方点都赋上一个点权。我们先假设固定点 \(a\) 和点 \(c\)，求有多少个点 \(b\) 满足条件。我们发现，只要 \(b\) 点在点 \(a\) 到点 \(c\) 的简单路径上的圆点或者方点所在的点双连通分量中的话，那么就一定是合法的。因为同一个点双中的两不同点 \(u,v\) 之间一定存在一条简单路径经过给定的在同一个点双内的另一点 \(w\)。所以我们可以将圆点的点权赋值为 \(-1\)，方点的点权赋值为所在点双的点的个数，这样合法的点就是路径上经过的点的点权之和。

所以现在问题转化为了：求出一棵树上任意两点之间路径上的点权和之和。这就转化成了一道树形 \(DP\) 题。我们可以把问题转化为计算每一个点的贡献。每一个点的贡献其实就是经过当前点的路径数量乘上当前点的权值，可以用类似于组合数学的统计方式来计算答案。因为是无向边，所以答案要乘以二。

还有一点需要注意，就是这道题给定的无向图不保证连通，所以还要考虑多个连通块的情况。总时间复杂度 \(O(n+m)\)。