「51nod 1618」树或非树

GG 是一张由 nn 个点和 nn 条边组成的无向图。 GG 中没有自环和重边。每条边有两种状态“开”和“关”。一开始,所有的边都是“关”着的。

现在有 mm 个操作 (v,u)(v,u) ,表示将从 vvuu 的最短路上的边改变状态(如果状态为“开”则变成“关”,反之,变成“开”)。如果 vvuu 存在多条最短路,则我们选取点序列字典序最小的那一条。

比如,将所有从 vvuu 的路径上的点表示成序列为 v,v1,v2,,uv,v_1,v_2,\cdots ,u 。那么我们从中取字典序最小的那一条。

在每一次操作后,你需要计算在图中由所有点和状态为“开”的边所组成图的连通块的数目。

Constraints

1n,m1000001\leq n,m \leq 100000

Solution

题目保证图是联通的,所以整个图为一棵环套树,去掉环之后则是森林。然后就可以 dfs 序链剖然后上线段树了,修改操作路径异或即可,其中环在线段树上要占用环大小的连续区间。

对于树来说,连通块个数即为点数 - 边数。询问时需要特判一下环上的情况,如果整个环都是开的,则 ans++ 。

Code

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<cstdio>
#include<algorithm>
#include<cstring>
#define lc (x<<1)
#define rc (x<<1|1)
#define LL long long
using namespace std;
const int N=1e5+5;
int n,m,cnt,tot,ctot,tim,son;
int x,y,L,R,dx,dy,ans;
int first[N],st[N],c[N],pos[N],be[N];
int fa[N],sz[N],deep[N],dfn[N],tp[N];
int s[N*8],tag[N*8];
bool vis[N];
struct edge{int to,next;}e[N*2];
int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}
void circle(int x,int fa)
{
vis[x]=true;st[++tot]=x;
for(int i=first[x];i;i=e[i].next)
{
int to=e[i].to;
if(to==fa)continue;
if(!vis[to])circle(to,x);
else
{
if(ctot)return;
y=0;while(y!=to)y=st[tot--],c[++ctot]=y;
}
}
tot--;
}
void dfs1(int x,int last)
{
sz[x]=1;deep[x]=deep[last]+1;
for(int i=first[x];i;i=e[i].next)
{
int to=e[i].to;
if(to==last||pos[to])continue;
fa[to]=x;be[to]=be[x];
dfs1(to,x);sz[x]+=sz[to];
}
}
void dfs2(int x,int top)
{
dfn[x]=++tim;tp[x]=top;son=0;
for(int i=first[x];i;i=e[i].next)
{
int to=e[i].to;
if(dfn[to]||pos[to])continue;
if(sz[to]>sz[son])son=to;
}
if(!son)return;
dfs2(son,top);
for(int i=first[x];i;i=e[i].next)
{
int to=e[i].to;
if(dfn[to]||pos[to])continue;
dfs2(to,to);
}
}
void down(int x,int l,int r)
{
if(!tag[x]||l==r)return;
tag[x]=0;int mid=(l+r)>>1;
tag[lc]^=1;tag[rc]^=1;
s[lc]=mid-l+1-s[lc];
s[rc]=r-mid-s[rc];
}
void modify(int x,int l,int r)
{
down(x,l,r);
if(L<=l&&r<=R)
{
s[x]=r-l+1-s[x];
tag[x]^=1;return;
}
int mid=(l+r)>>1;
if(L<=mid)modify(lc,l,mid);
if(R>mid)modify(rc,mid+1,r);
s[x]=s[lc]+s[rc];
}
int query(int x,int l,int r)
{
down(x,l,r);
if(L<=l&&r<=R)return s[x];
int mid=(l+r)>>1,sum=0;
if(L<=mid)sum+=query(lc,l,mid);
if(R>mid)sum+=query(rc,mid+1,r);
return sum;
}
void open(int x,int y)
{
if(x>y)return;
L=x;R=y;modify(1,1,n+ctot);
}
void change(int x,int y)
{
while(tp[x]!=tp[y])
{
if(deep[tp[x]]<deep[tp[y]])swap(x,y);
open(dfn[tp[x]],dfn[x]);x=fa[tp[x]];
}
if(deep[x]<deep[y])swap(x,y);
open(dfn[y]+1,dfn[x]);
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
{
x=read();y=read();
ins(x,y);ins(y,x);
}
circle(1,-1);
for(int i=1;i<=ctot;i++)pos[c[i]]=i;
for(int i=1;i<=ctot;i++)
{
be[c[i]]=c[i];
dfs1(c[i],c[i]);dfs2(c[i],c[i]);
}
while(m--)
{
x=read();y=read();
if(be[x]==be[y])
{
change(x,y);
ans=n-s[1];L=n+1;R=n+ctot;
if(query(1,1,n+ctot)==ctot)ans++;
printf("%d\n",ans);
continue;
}
change(x,be[x]);change(y,be[y]);
x=be[x];y=be[y];dx=pos[x];dy=pos[y];
if(dx<dy)
{
if(dy-dx>ctot+dx-dy||(dy-dx==ctot+dx-dy&&c[dx+1]>c[(dx-2+ctot)%ctot+1]))
open(n+1,n+dx),open(n+dy+1,n+ctot);
else open(n+dx+1,n+dy);
}
else
{
if(dx-dy>ctot+dy-dx||(dx-dy==ctot+dy-dx&&c[dx-1]>c[dx%ctot+1]))
open(n+1,n+dy),open(n+dx+1,n+ctot);
else open(n+dy+1,n+dx);
}
ans=n-s[1];L=n+1;R=n+ctot;
if(query(1,1,n+ctot)==ctot)ans++;
printf("%d\n",ans);
}
return 0;
}