[template] [Luogu p4630] duathlon Triathlon (round square tree)

Duathlon Iron man two

Topic link ：luogu P4630

The main idea of the topic

Here's an undirected graph , Then you can choose three points in order a,b,c, Guarantee a You can go to b,b You can go to c, And there is a scheme that makes the intersection of these two paths only b.
Then ask how many satisfied triples you have .

Ideas

First of all, if this is a forest, we can do it well .
（ Anyway, all kinds of methods are up to you ）

Now we are a picture , That's not easy .
Then let's consider whether we can turn it into a tree ？ So we can use the round square tree .

---

Round square tree

Before talking about the round square tree , Let's give some definitions first ：

Vertex biconnected graph

If it's a digraph , There is a strongly connected graph . The undirected graph will have a point biconnected graph and an edge biconnected graph .
Edge biconnected subgraphs are not used here , We give the definition of vertex biconnected subgraph ： There are at least two paths between any two different points in the graph that do not repeat .
（ Because it is difficult to make a point, we default that there is no isolated point , If there is one in the title, special treatment shall be carried out according to the requirements of the title ）

Then you will find that there is an approximate equivalent definition of a graph without cut points .
It is found that the counterexample has only two points and one edge （ Or you can think it's not a counterexample , Because you must repeat the beginning and the end ）

Point biconnected component

Like strongly connected components , It is a maximal vertex biconnected subgraph of a graph .
But if you draw a picture, it is not difficult to find that a point may be in several point pairs , But one side can only be in one .

Round square tree

That's in the round square tree , We regard the original point as the origin , Each dot pair corresponds to a square dot .
（ It is not difficult to see that the maximum number of square points is $n$, So remember to drive in total $2n$）
Then a square point points to it the point inside the double （ origin ） Even the edge .
Then the picture becomes several squares of chrysanthemums , Each chrysanthemum is connected by the cut point of the original drawing .

Then you can easily imagine that the paths on any set of trees are crisscrossed with circles and square dots .

build

Consider using similar Tarjan Methods .
That's because the undirected graph , So we update when we find new points $low$ with $low$ to update , When you find the original point, follow $dfn$ to update .
Then you will find that it is also the top of the ring , The condition is $df{n}_u=lo{w}_x$（ then $u$ It's the top ）

Then you can build it .

This question

If it's a tree, it's easy to do , We consider making the ring into a tree through a round square tree , Then see how to deal with the square point .

Then we will actually find that you are between any two points in a dot pair , For every other point, there is a way to walk .
（ The little proof is that you can pull this dot pair into a ring , And then it's gone ）

Then you will find that if you want to pass a square point , You can pass any dot inside , Then we can assign the weight of the square point to the size of its dot pair , Then the sum of the weights of the square points on the path is fixed $s,f$ Satisfied $c$ The number of .
Then you find that you are too heavy , Because two adjacent square points are connected by points , So each point actually acts as a connection location , So we need to make the weight of the point $-1$.

Then here are all the requirements , We just have a small tree DP once , Consider the contribution of each point to all paths containing it .
（ Inside the subtree , Subtree and outside ）

Code

#include<cstdio>
#include<vector>
#include<iostream>
#define ll long long

using namespace std;

const int N = 1e5 + 100;
int n, m;
vector <int> G[N];

struct YF_tree {
    
	int dfn[N], low[N], sta[N], tot, deg[N << 1], fa[N << 1][21];
	int val[N << 1], num, sz[N << 1];
	vector <int> GG[N << 1];
	ll ans;
	
	void link(int x, int y) {
    
		GG[x].push_back(y); GG[y].push_back(x);
	}
	
	void tarjan(int now) {
    
		dfn[now] = low[now] = ++dfn[0]; sta[++sta[0]] = now; num++;
		for (int i = 0; i < G[now].size(); i++) {
     int x = G[now][i];
			if (!dfn[x]) {
    
				tarjan(x); low[now] = min(low[now], low[x]);
				if (dfn[now] == low[x]) {
    
					tot++;
					while (sta[sta[0]] != x) {
    
						link(sta[sta[0]], tot);
						sta[0]--; val[tot]++;
					}
					link(sta[sta[0]], tot); sta[0]--; val[tot]++;
					link(now, tot); val[tot]++;
				}
			}
			else low[now] = min(low[now], dfn[x]);
		}
	}
	
	void dfs(int now, int father) {
    
		if (now <= n) sz[now] = 1;
		for (int i = 0; i < GG[now].size(); i++) {
     int x = GG[now][i];
			if (x != father) {
    
				dfs(x, now);
				ans += 2ll * sz[now] * sz[x] * val[now];
				sz[now] += sz[x];
			}
		}
		ans += 2ll * sz[now] * (num - sz[now]) * val[now];
	}
	
	void Init() {
    
		tot = n; for (int i = 1; i <= n; i++) val[i] = -1;
		for (int i = 1; i <= n; i++) if (!dfn[i]) num = 0, tarjan(i), dfs(i, 0);
	}
}T;

int main() {
    
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
    
		int x, y; scanf("%d %d", &x, &y);
		G[x].push_back(y); G[y].push_back(x);
	}
	
	T.Init();
	
	printf("%lld", T.ans);
	
	return 0;
}