cometOJ#0C.项链与计数(并查集)

Posted on   |   In

题目描述

在图论中，“简单环” 被定义为一个点数和边数相等的回路，并且这条回路上没有出现重复的点或边。

对于一个无向图，小象定义 “项链” 是由一些简单环组成的子图，不妨设项链包括 k 个简单环 $C_1, C_2, \ldots…, C_k (k \in \mathbb{N}^+)$，那么项链需要满足：

  • 当且仅当 $|i - j| \leq 1$ 时，简单环 $C_i $和 $C_j $共用顶点；
  • 简单环 $C_i$和 $C_{i +1}$恰好共用一个顶点；
  • 任意两个不同的简单环 $C_i$和 $C_j(i \neq j)$ 没有共用边。

注意，按照上述定义，一个简单环也可以看做是项链。

小象画了一个 $n$个点的无向图，其中点被从 $1$到 $n$ 编号。最开始图中没有任何一条边，然后他往图中依次添加了 $m$ 条无向边，整个图逐渐变得复杂起来。

他很好奇，在他每添加了一条边之后，整个图里存在多少对点 $(u, v)$满足 $u \neq v$且存在一个项链 $C_1,C_2, \ldots…, C_k$使得 $u \in C_1$, $v \in C_k$。需要一提的是，小象认为 $(u, v)$ 和 $(v, u)$ 是相同的点对。

不妨设在添加了 $i$ 条边后这样的点对数量为 $f(i)$,小象希望你能帮他计算 $\bigoplus\limits_{i = 1}^{m}{(i \cdot f(i))}$的值，这里$ \oplus​$ 表示按位异或运算符

题解

对于所有的边 构造生成树

对于所有边根据生成树的形态 分成树边和非树边

对于加入树边 不会对答案产生影响

对于加入非树边 则这个树链上任意两点都是满足条件的 我们可以用并查集缩点 并在缩点的过程中维护价值即可

复杂度$O(n+m)$

代码实现

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
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,double>
//#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=1e6+10;
const double eps=1e-4;
#define ll long long
using namespace std;
const int inf=1e9;
//struct edge{int t;double v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
//void add(int x,int y,double vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
struct FastIO
{
    static const int S=200;
    int wpos;
    char wbuf[S];
    FastIO():wpos(0){}
    inline int xchar()
    {
        static char buf[S];
        static int len=0,pos=0;
        if(pos==len) pos=0,len=fread(buf,1,S,stdin);
        if(pos==len) exit(0);
        return buf[pos++];
    }
    inline int read()
    {
        int s=1,c=xchar(),x=0;
        while(c<=32) c=xchar();
        if(c=='-') s=-1,c=xchar();
        for(;'0'<=c&&c<='9';c=xchar()) x=x*10+c-'0';
        return x*s;
    }
    ~FastIO()
    {
        if(wpos) fwrite(wbuf,1,wpos,stdout),wpos=0;
    }
}io;
vector<int>vec[MAXN];
int f[MAXN],sz[MAXN];
bool vis[MAXN];
int find1(int x){
	if(x==f[x])return x;
	else return f[x]=find1(f[x]);
}

int fa[MAXN],dep[MAXN];

void dfs(int x,int pre,int deep){
	fa[x]=pre;dep[x]=deep+1;vis[x]=1;
	for(int i=0;i<vec[x].size();i++){
		if(vec[x][i]==pre)continue;
		dfs(vec[x][i],x,deep+1);
	}
}
typedef struct node{
	int x,y;
}node;
node d[MAXN<<1];
bool T[MAXN<<1];
int main(){
	int _=io.read();
	while(_--){
		int n=io.read();int m=io.read();
		inc(i,1,n)f[i]=i;
		inc(i,1,n)vec[i].clear(),vis[i]=0;
		inc(i,1,m)T[i]=0;
		inc(i,1,m){
			d[i].x=io.read();d[i].y=io.read();
			int t1=find1(d[i].x);int t2=find1(d[i].y);
			if(t1==t2)continue;
			f[t1]=t2;T[i]=1;
			vec[d[i].x].pb(d[i].y);
			vec[d[i].y].pb(d[i].x);
		}
		inc(i,1,n)if(!vis[i])dfs(i,0,0);
		inc(i,1,n)f[i]=i,sz[i]=1;
		ll ans=0,sum=0,ans1=0;
		int x,y;
		inc(i,1,m){
			if(T[i]){ans^=sum*i;continue;}
			x=d[i].x;y=d[i].y;
			if(f[x]==f[y]){ans^=sum*i;continue;}
			ans1=0;x=find1(x);y=find1(y);
			while(x!=y){
				if(dep[x]<dep[y])swap(x,y);
				ans1+=sz[x];
				sum-=1ll*sz[x]*(sz[x]-1)/2;
				f[x]=fa[x];
				x=find1(x);
			}
			x=find1(x);
			sum-=1ll*sz[x]*(sz[x]-1)/2;sz[x]+=ans1;
			sum+=1ll*sz[x]*(sz[x]-1)/2;
			ans^=sum*i;
		}
		printf("%lld\n",ans);
	}
	return 0;
}