今天学习了圆方树，并且做了一道和这道题很像的题，于是就又来做了一下这道题。题意给定一张不保证连通的无向图。求有多少个点对\((a,b,c)\)满足\(a\)到\(c\)的简单路径上经过了点\(b\)。思路显然圆方树。点双缩点过后构造一颗圆方树，然后考虑如何计算答案。圆方树有一个实

具体思路题目问的是三元组\((x,z,y)\)使得\(x\)可以到达\(z\)，且\(z\)可以到达\(y\)，求三元组\((x,z,y)\)的数量。我们转化一下问题，就是问\(x,y\)之间所有不重复路径的点的并集减\(2\)。显然，无向图中任意一个点都属于一个点双连通分量。那么问题转化为\(x,y\)之

一、题目描述：给你一个$n$个点，$m$条边的无向图。图不一定联通求出点对$(u,c,v)$的数量，使得点$u$存在一条经过点$c$到达点$v$的无向图。数据范围：$1\len\le1\times10^5,1\lem\le2\times10^5$ 二、解题思路：算是圆方树比较模板的题了

APIO2018~2022做题记录1.[APIO2021]封闭道路题意：一棵大小为\(n\)的树，有边权，设\(f(x)\)表示要满足所有点的\(deg\leqslantx\)所要删掉的边的边权和的最小值，求出\(f(0)\)到\(f(n)\)思路：先考虑对于每个\(x\)计算答案。设\(dp[i][0/1]\)表示\(i\)向上连的边删或不删时的最小代价

题意：问有多少点(x,y,z)满足从x出发经过y到z。且点不能重复经过。题解：前置芝士1：点双有个性质：两点之间简单路径的并集刚好等于这个点双(证明用网络流模型)等价不同点uv

码力底下，思维迟钝，我该怎么办？还是说这题太毒？题意给定一个\(n\)个商店，第\(i\)个商店的类型为\(t_i\)，在\([a_i,b_i]\)时间营业，位于位置\(x_i\)。定义某一时刻一