铁人专题

铁人两项

铁人两项 求出三元组(s,c,f)的个数,使得在图中从s到c到f有一条简单路径。 考虑如果是树的话怎么做。若选出两点s和f的话,三元组的个数就要加上s和f之间的所有点。那么,换个思路,我们可以考虑每个点被统计到的次数(难道这就是所谓转换法吗?!)。那么一个树形dp就解决了。 但是,这是个图,怎么办呢?我们发现我们可以直接把点双缩起来,然后把某个点双的值改为点双中的点数。但是,别忘记点双不能缩