题意:求满足如下条件的有序三元组个数$(u,v,w)$且u到v的路径与v到w的路径不重叠。
对原图建立圆方树，然后枚举中间点m,如果存在两个点u和v,满足u到m的路径和v到m的路径不经过同一个圆点。
考虑容斥，枚举中间点m，然后计算除了m之外的总的有序点对数，然后减掉到达m必须要经过同一个点的点对数
如何容斥？
考虑一个方点u的所有相邻的圆点v,v的子树内的一个点对，要想到达u除了v之外的一个相邻节点，则必须经过v。
所以对于每个方点u，统计其所有相邻圆点v子树内的有序点对数，然后乘u的相邻节点个数-1，即为u的每个相邻节点应该减掉的值的和。
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <assert.h>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
#define debug(x) cout << #x << " = " << x << endl;
const int_t LARGE = 300000;
constexpr inline int_t C2(int_t x)
{
return x * (x - 1) / 2;
}
struct Edge
{
int_t v1, v2;
};
int_t n, m;
std::vector<int_t> graph[LARGE + 1];
std::vector<int_t> tree[LARGE + 1];
std::vector<int_t> BCC[LARGE + 1];
std::stack<Edge> stack;
int_t size[LARGE + 1];
bool isCut[LARGE + 1];
int_t DFSN[LARGE + 1];
int_t LOW[LARGE + 1];
int_t BCCID[LARGE + 1];
int_t parent[LARGE + 1];
int_t block[LARGE + 1];
int_t nextVtx;
void DFS(int_t vtx, int_t from = -1)
{
DFSN[vtx] = LOW[vtx] = ++DFSN[0];
int_t chdCount = 0;
for (int_t to : graph[vtx])
{
if (to == from)
continue;
if (DFSN[to] == 0)
{
stack.push(Edge{vtx, to});
chdCount++;
DFS(to, vtx);
LOW[vtx] = std::min(LOW[vtx], LOW[to]);
//判断不能写LOW[vtx]>=DFSN[vtx],否则会把一棵不是BCC的子树算重
if (LOW[to] >= DFSN[vtx])
{
isCut[vtx] = true;
int_t id = ++BCCID[0];
int_t next = ++nextVtx;
while (true)
{
auto top = stack.top();
stack.pop();
if (BCCID[top.v1] != id)
{
BCCID[top.v1] = id;
BCC[id].push_back(top.v1);
tree[next].push_back(top.v1);
tree[top.v1].push_back(next);
}
if (BCCID[top.v2] != id)
{
BCCID[top.v2] = id;
BCC[id].push_back(top.v2);
tree[next].push_back(top.v2);
tree[top.v2].push_back(next);
}
if ((top.v1 == vtx && top.v2 == to) || (top.v1 == to && top.v2 == vtx))
break;
}
}
}
//只判断后向边，防止算重
else if (DFSN[to] < DFSN[vtx])
{
stack.push(Edge{vtx, to});
LOW[vtx] = std::min(LOW[vtx], DFSN[to]);
}
}
if (from == -1 && chdCount == 1)
isCut[vtx] = false;
}
void DFS1(int_t vtx, int_t block, int_t from = -1, int_t depth = 1)
{
static bool visited[LARGE + 1];
if (visited[vtx])
return;
parent[vtx] = from;
visited[vtx] = true;
size[vtx] = (vtx <= n);
::block[vtx] = block;
for (int_t to : tree[vtx])
{
if (visited[to])
continue;
DFS1(to, block, vtx, depth + 1);
size[vtx] += size[to];
}
}
int main()
{
cin >> n >> m;
for (int_t i = 1; i <= m; i++)
{
int_t v1, v2;
cin >> v1 >> v2;
graph[v1].push_back(v2);
graph[v2].push_back(v1);
}
nextVtx = n;
std::vector<int_t> roots;
for (int_t i = 1; i <= n; i++)
{
if (DFSN[i] == 0)
{
DFS(i);
DFS1(i, i);
roots.push_back(i);
}
}
for (int_t i = 1; i <= nextVtx; i++)
{
auto &curr = tree[i];
std::sort(curr.begin(), curr.end());
curr.resize(std::unique(curr.begin(), curr.end()) - curr.begin());
}
//我放弃排列组合了
int_t result = 0;
for (int_t i = 1; i <= n; i++)
{
result += C2(::size[::block[i]] - 1) * 2;
}
for (int_t i = n + 1; i <= nextVtx; i++)
{
for (int_t vtx : tree[i])
{
if (vtx == parent[i])
{
result -= (tree[i].size() - 1) * C2(size[block[i]] - size[i]) * 2;
}
else
{
result -= (tree[i].size() - 1) * C2(size[vtx]) * 2;
}
}
}
cout << result << endl;
return 0;
}
