给定一个$n$个点$m$条边无向图$G$, 问有多少点对$(u,v)$满足有$(1 \to u)$的路径以及$( 1 \to v)$的路径，并且两条路径除了$1$没有其他交点
你妹就一dominator tree裸题
正难则反。观察到直接数这些点对不方便，那么可以换个思路，数那些除了$1$还有其他交点的路径。
首先肯定是以$1$为根搞出一个Flow Graph
如果两个点的路径除了$1$还有其他交点$x$，$x$是有向图的一个割点
所以我们套用dominator tree求一下有向图割点就好了。
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
#define pb push_back
#define bug(x) cout<<#x<<"="<<x<<" "
#define debug(x) cout<<#x<<"="<<x<<endl
typedef long long ll;
typedef vector<int> vec;
const int M=1e5+5;
vec pre[M],G[M],dom[M];
inline void rd(int &a){
a=0;char c;
while(c=getchar(),!isdigit(c));
do a=a*10+(c^48);
while(c=getchar(),isdigit(c));
}
int dfn[M],tid[M],anc[M],dfs_clock;
int idom[M],semi[M],best[M],f[M];
inline void predfs(int v){
dfn[v]=++dfs_clock,tid[dfs_clock]=v;
semi[dfs_clock]=anc[dfs_clock]=best[dfs_clock]=dfs_clock;
for(int i=0;i<G[v].size();++i){
int to=G[v][i];
if(!dfn[to])predfs(to),f[dfn[to]]=dfn[v];
}
}
int sz[M];
inline void dfs(int v){
sz[v]=1;
for(int i=0;i<dom[v].size();++i){
int to=dom[v][i];
dfs(to);
sz[v]+=sz[to];
}
}
inline int get(int x){
if(anc[x]==x)return x;
int y=get(anc[x]);
if(semi[best[x]]>semi[best[anc[x]]])best[x]=best[anc[x]];
//maintain
anc[x]=y;//path compression
return y;
}
inline void Min(int &a,int b){
if(a>b)a=b;
}
int main(){
int n,m;cin>>n>>m;
for(int i=1,a,b;i<=m;++i){
rd(a),rd(b);
G[a].pb(b),pre[b].pb(a);
}
predfs(1);
for(int y=dfs_clock;y>1;--y){
int x=f[y],w=tid[y];
for(int i=0;i<pre[w].size();++i){
int z=dfn[pre[w][i]];
if(!z)continue;
get(z);
Min(semi[y],semi[best[z]]);
}
dom[semi[y]].pb(y);
anc[y]=x;
for(int i=0,z;i<dom[x].size();++i){
z=dom[x][i];
get(z);
if(semi[best[z]]<x)idom[z]=best[z];
else idom[z]=x;
}
dom[x].clear();
}
for(int i=2;i<=dfs_clock;++i){
if(idom[i]!=semi[i])idom[i]=idom[idom[i]];
dom[idom[i]].pb(i);
}
ll res=(ll)(dfs_clock-1)*dfs_clock>>1ll;
for(int i=0;i<dom[1].size();++i){
int to=dom[1][i];
dfs(to);
res-=(ll)sz[to]*(sz[to]-1)>>1ll;
}
cout<<res<<endl;
return 0;
}