【LGR114C】地地铁铁

题意：

给定 $n$ 个点 $m$ 条边的无向连通图，每条边标有 $0$ 或 $1$，统计无序点对 $(x,y)$ 的数量，满足 $x,y$ 之间存在一条简单路径（点不重），使得这条简单路径既经过 $0$ 边也经过 $1$ 边。

$n\le 4\times 10^5$，$m\le 10^6$。

题解：

首先变为统计 $(x,y)$ 之间任意简单路径都只经过 $0$ 边或只经过 $1$ 边的 $(x,y)$ 的对数。

分类讨论，考虑 $(x,y)$ 之间所有简单路径都只经过 $0$ 边的点对数量。

借着这个机会，系统总结一下几个点双的基本性质。接下来我们称 “非平凡点双” 为点数 $\ge 3$ 的点双。

• 引理 1：对于非平凡点双 $S$ 和任意 $S$ 内两个不同的点 $a,b$，存在两条 $a,b$ 间的点不交（除 $a,b$ 外，以后将不再说明此事）的简单路径 $A,B$。

  注意点双的定义是：删掉任意一个点后原图仍连通。所以这个引理不是废话（

  证明：考虑对 $a,b$ 间的最短路 $d(a,b)$ 归纳证明。

  当 $d(a,b)=1$ 即存在边 $(a,b)$ 时。若不存在另外一条 $a,b$ 间的路径，那么删掉边 $(a,b)$ 后 $a,b$ 将不连通，不妨设此时 $a$ 所在的连通块大小 $\ge 2$，那么在原图中删掉 $a$ 将会导致原图不连通，矛盾。

  当 $d(a,b)>1$ 时。考虑 $a,b$ 间的任意一条最短路 $a-\cdots -c-b$。根据假设，存在两条 $a,c$ 间的点不交简单路径 $A,B$。根据定义，删去 $c$ 后 $a,b$ 仍然连通，此时取一条 $a,b$ 间的简单路径 $P$，那么 $P$ 不经过 $c$。如图：

  

  不妨设 $P$ 和 $A,B$ 第一次相交在 $B$ 上的点 $d$，那么 $b\stackrel{P}{\to }d\stackrel{B}{\to }a$ 和 $b\to c\stackrel{A}{\to }a$ 即为两条点不交的所求路径。

• 推论 2：对于点数 $\ge 3$ 的图 $G$，$G$ 是点双连通分量当且仅当对于任意 $G$ 中的两个不同的点 $a,b$，存在两条 $a,b$ 间的点不交的简单路径 $A,B$。

• 引理 3：对于点双 $S$ 和任意 $S$ 内三个不同的点 $a,b,c$（这蕴含 $S$ 是非平凡的），存在一条简单路径依次经过 $a,b,c$。

  证明：如图，任取两条 $a,b$ 间的点不交的简单路径 $A,B$，再任取一条 $b,c$ 间的且不经过 $a$ 的路径 $P$，根据点双的定义，这三条路径都是可以取得到的。

  

  不妨设 $P$ 与 $A,B$ 最后一次相交在 $B$ 上的点 $d$（那么 $d\ne a$），于是 $a\stackrel{A}{\to }b\stackrel{B}{\to }d\stackrel{P}{\to }c$ 即为一条所求路径。

• 引理 4：对于非平凡点双 $S$ 和任意 $S$ 内的一点 $u$ 和一边 $e$，存在一个经过 $u,e$ 的简单环。

  证明：设 $e=(a,b)$。若 $u=a$ 或 $u=b$ 则显然；否则，根据引理 3，存在一条简单路径 $P$ 依次经过 $a,u,b$，显然 $P$ 不经过 $e$，于是 $P,e$ 组成的简单环即为一条所求的环。

• 引理 5：对于点双 $S$ 和任意 $S$ 内两个不同的点 $a,b$ 和一边 $e$，存在一条 $a,b$ 间的简单路径经过 $e$。

  证明：若 $S$ 中只有两个点的情况那么证明显然，所以不妨设 $S$ 是非平凡点双。

  设 $e=(u,v)$。根据引理 4，存在一个经过 $a,e$ 的简单环 $C$，不妨将 $C$ 上 $a-u$ 段称为 $A$，$a-v$ 段称为 $B$。如图：

  

  任取一条从 $b$ 出发不经过 $a$ 的与 $C$ 相交的简单路径 $P$（为什么一定能取到？考虑取一条 $b,u$ 间的不经过 $a$ 的简单路径即可）

  不妨设 $P$ 与 $C$ 第一次相交在 $A$ 上的点 $c$（那么 $c\ne a$），于是 $b\stackrel{P}{\to }c\stackrel{A}{\to }u\stackrel{e}{\to }v\stackrel{B}{\to }a$ 即为一条所求路径。

引理 3 和引理 5 是两个很常用的结论。

看回这题，考虑将原图缩成点双，那么若 $x,y$ 间存在某个有 $1$ 边的点双，那么根据引理 5，$x,y$ 间就一定有经过 $1$ 边的简单路径。反之，若 $x,y$ 间所有点双都只有 $0$ 边，那么 $x,y$ 间的所有简单路径肯定都只包含 $0$ 边。

有了这个结论后剩下就好做了。具体地，先建出圆方树。然后对于原图上一条 $0$ 边 $(u,v)$，它恰属于一个点双 $S$，找到 $S$ 对应的方点只需在圆方树上根据 $u,v$ 相对位置讨论即可，然后我们再给该方点打上标记。接下来统计圆方树上不经过标记点的圆点间路径数即可。

于是我们解决了 “$(x,y)$ 之间所有简单路径都只经过 $0$ 边的点对数量”，对于只经过 $1$ 边的同理统计。

接下来统计 $(x,y)$ 之间既有只经过 $0$ 边的路径（称为 $0$ 路）、又有只经过 $1$ 边的路径（称为 $1$ 路）的点对数量，称这种点对为 “合法点对”。

• 命题 6：若 $(x,y)$ 为合法点对，那么 $x,y$ 之间的任意一条 $0$ 路和任意一条 $1$ 路都不交（除 $x,y$ 外）。

  证明：否则可以调整得到一条 $01$ 路。

• 推论 7：若 $(x,y)$ 为合法点对，那么 $x,y$ 肯定同在一个点双 $S$ 内，进一步地，$S$ 肯定是非平凡点双。

考虑对某个非平凡点双 $S$ 统计其内的合法点对 $(x,y)$ 的数量。

一个直觉（出题人说有，但我没有，怎么会事呢？）是，点双 $S$ 肯定长成这样：

接下来我们来证明这一点。

我们称 $S$ 内的一点 $u$ 为交错点，当且仅当 $u$ 在 $S$ 内既存在相邻的 $0$ 边，也存在相邻的 $1$ 边。

• 命题 8：若 $(x,y)$ 为 $S$ 内的合法点对。对于 $S$ 内的任意交错点 $u$，$x,y$ 中必有一者等于 $u$。

  证明：反证，若 $x,y,u$ 为三个不同的点。设与 $u$ 相邻的 $0$ 边为 $(u,a)$，与 $u$ 相邻的 $1$ 边为 $(u,b)$。根据引理 5，存在两条 $x,y$ 间简单路径，其中一条 $A$ 经过 $(u,a)$，其中一条 $B$ 经过 $(u,b)$。如图：

  

  由于 $(x,y)$ 为合法点对，那么可知 $A$ 为 $0$ 路且 $B$ 为 $1$ 路，但它们相交在点 $u$，根据命题 6 可知矛盾。

• 推论 9：若 $S$ 内存在合法点对，则 $S$ 内至多有 $2$ 个交错点。

• 推论 10：若 $S$ 内存在合法点对，则 $S$ 内恰有 $2$ 个交错点。

  证明：若 $S$ 只有一个交错点，容易证明该交错点是割点，矛盾。

• 命题 11：若 $S$ 内恰有 $2$ 个交错点 $x,y$，那么 $S$ 内恰有一对合法点对 $(x,y)$。

  证明：对于任意 $S$ 内的合法点对 $(x^{\prime },y^{\prime })$，根据命题 8 可知，$x^{\prime },y^{\prime }$ 中必有一者等于 $x$，且必有一者等于 $y$，那么 $(x^{\prime },y^{\prime })=(x,y)$。

  从而只需证明 $(x,y)$ 为合法点对即可：根据引理易知，$x,y$ 之间肯定既有包含 $0$ 边的路径、也有包含 $1$ 边的路径，于是只需证明 $x,y$ 间不存在既包含 $0$ 边也包含 $1$ 边的路径即可。而若出现了这种路径，显然能找到另一个不同于 $x,y$ 的交错点，矛盾。

于是，我们证明了，某个非平凡点双 $S$ 内包含合法点对，当且仅当 $S$ 中恰有 $2$ 个交错点，且此时 $S$ 中恰包含一个合法点对。

于是我们可以线性处理整个问题。具体地，对于原图上一条边 $(u,v)$，找到其所在点双在圆方树上对应点 $S$，我们给树上 $(u,S),(v,S)$ 这两条边分别标上 $(u,v)$ 所属颜色的记号，那么最后若 $(u,S)$ 上既有 $0$ 记号又有 $1$ 记号，就意味着 $u$ 是 $S$ 内的交错点。

ll C2(int x){return 1ll*x*(x-1)/2;}

struct edge
{
	int u,v;
	bool c;
}e[M];

int n,m;
int top,sta[N];
int idx,dfn[N],low[N];
int node,fa[N<<1],dep[N<<1];
int tag[N<<1],tot[N<<1];
ll ans;

vector<int> e1[N],e2[N<<1];

void tarjan(int u)
{
	dfn[u]=low[u]=++idx;
	sta[++top]=u;
	for(int v:e1[u])
	{
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
				int S=++node,w;
				do
				{
					w=sta[top],top--;
					e2[S].push_back(w),e2[w].push_back(S);
				}while(w!=v);
				e2[S].push_back(u),e2[u].push_back(S);
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
}

void dfs(int u)
{
	for(int v:e2[u]) if(v!=fa[u])
		fa[v]=u,dep[v]=dep[u]+1,dfs(v);
}

int findS(int u,int v)
{
	return fa[dep[u]<dep[v]?v:u];
}

int dfs1(int u)
{
	int size=(u<=n);
	for(int v:e2[u]) if(v!=fa[u])
		tag[u]?(ans+=C2(dfs1(v))):(size+=dfs1(v));
	return size;
}

void calc1(bool c)
{
	for(int i=1;i<=m;i++)
		if(e[i].c^c) tag[findS(e[i].u,e[i].v)]=1;
	ans+=C2(dfs1(1));
	for(int i=1;i<=node;i++) tag[i]=0;
}

void calc2()
{
	for(int i=1;i<=m;i++)
	{
		int S=findS(e[i].u,e[i].v);
		tag[dep[e[i].u]<dep[S]?S:e[i].u]|=(1<<e[i].c);
		tag[dep[e[i].v]<dep[S]?S:e[i].v]|=(1<<e[i].c);
	}
	for(int i=1;i<=node;i++)
		if(tag[i]==3) tot[i]++,tot[fa[i]]++;
	for(int i=n+1;i<=node;i++)
		if(tot[i]==2) ans++;
}

int main()
{
	read(),n=node=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		e[i].u=read(),e[i].v=read(),e[i].c=(getchar()=='D');
		e1[e[i].u].push_back(e[i].v),e1[e[i].v].push_back(e[i].u);
	}
	tarjan(1);
	dfs(1);
	calc1(0);
	calc1(1);
	calc2();
	printf("%lld\n",C2(n)-ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99