本文从WordPress迁移而来, 查看全部WordPress迁移文章
hdu 4338 和 uva 12616 差不多一样,主要是都使用相同的方法来进行缩点和拆点建树
关于具体的步骤,可以参考 uva 12616 的题解,这里只说一下本题
本题的区别是,更改cal函数
uva中,comnum是指,一个连通块中,非割点数的数量
hdu中,comnum是指,整个连通块的点数
那么在统计过程中,肯定会出现重复统计割点的情况,本题采用的是减掉重复割点的方法,在treedp中需要继续路径中割点的数量,在求出lca后,减掉路径上的割点数即可
求lca的方法,用在线倍增算法(不是转化为RMQ),模板来自AcRush
1 |
|