题面 第一次写圆方树的题,感觉好难理解啊… 所谓圆方树就是为图中的点双联通分量建一个方点,忽略点双联通分量中原来的边,改为点双联通分量中所有的点向该方点连边. 本题中可以为所有联通块建出圆方树. 考虑以下树形DP: 以当前遍历到的点为 c c c点计算经过它的路径. 此题中一个点的贡献为经过它的路径乘以其权值 每个原点相邻的都是方点,每个方点的权值为其代表的点双联通分量的点数,这样一来每个圆点作为 s s s和 c c c,和以之作为 c c c和 f f f的方案都会被多算一次,因此将原点的方案设为 − 1 -1 −1 Code
