收回我以前对某些题的评论– 这一道 tmd 才是最恶心的。
苟活者在淡红的 WA 中会依稀看见微茫的希望，真正的傻 B 会更奋然而 AC。– 某树人
耗时 4.5 个小时，手写 180 行代码，套用 5 种模板，定义 16 个数组，提交近 10 次，终于 AC…
题意：
给定一个联通图，有 2 种操作，删边和询问两点之间有几条边去掉之后两点不再联通。保证图一直联通。（点数<=30000, 边数<=100000, 操作<=40000）
思路：
1. 对于删边操作，我们不妨倒过来处理，变成加边。
2. 如果图中有环，那么显然这个环上的每个边去掉之后图都是联通的，因此我们将环缩成点处理，这时两点间的距离就是每个询问的答案。而两点之间的距离就是 dis(a,b)=dep(a)+dep(b)-2dep(lca)
3. 每次添边时把形成的环缩成点，每个点显然只会缩一次，缩完了作为一个新点和别人一起缩，因此缩点的均摊复杂度是 O(1) 的。
4. 每次把环上的点缩到深度最小的点上去，这样对点深度的维护很有利。
5. 利用 dfs 序把每个点映射到一个线段树里去，每一棵子树代表的区间就是 [a,b]，a,b 分别为子树中最小和最大节点编号。
6. 每次将一个点缩点，就是将它和它的子树的深度降为缩点后的值。
7.LCA 可以预处理出倍增的数组，每次 logn 询问 LCA。
8. 线段树可以标记永久化。
总结以上思路发现：
1. 我们需要涉及到动态的缩点、联通性的判断、dfs 序的维护、点集的维护。因此我们需要至少 4 个数组维护这些映射的信息。
2. 光是并查集就要写两个。
3. 我们还需要一个 set 判断边是否被删过。
4. 我们也许需要用 tarjan 进行第一次缩点 (分析发现可以不用)。
5. 我们会套很多的模板，打很多的代码。
6. 这是一道省选题。(你 TM 省选考这玩意)
不过我还是耐着性子打完了
然后狂 WA(数组开小了 TMD 会 WA)
AC 代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>
#define MX 30002
#define ME 100001
#define ls (node<<1)
#define rs (node<<1|1)
#define mid ((l+r)>>1)
using namespace std;
int dp[MX];
int anc[MX][21];
int fst[MX],nxt[ME],v[ME],lnum=-1;
int srcu[ME],srcv[ME];
int n,m,q;
int fa[MX];
int color[MX];
int suoa[ME],suob[ME],suon;
int findfa(int x){return fa[x]==x?x:fa[x]=findfa(fa[x]);}
int ranks[MX],nowr;
int lranks[MX],rranks[MX];
int belong[MX],trefa[MX];
int findbel(int x){return x==belong[x]?x:belong[x]=findbel(belong[x]);}
typedef struct qurd
{
int a,b,c,ans;
}requires;
typedef struct asdf
{
int l,r,add,sum;
}segments;
typedef pair<int,int>pii;
requires qur[ME];
segments dep[MX<<2];
set<pii>isdel;
void addeg(int nu,int nv)
{
nxt[++lnum]=fst[nu];
fst[nu]=lnum;
v[lnum]=nv;
}
void build(int node,int l,int r)
{
dep[node].l=l,dep[node].r=r;
dep[node].add=0;
dep[node].sum=0;
if(l==r)return;
else build(ls,l,mid),build(rs,mid+1,r);
}
void add(int node,int ql,int qr,int x)
{
int l=dep[node].l,r=dep[node].r;
if(ql<=l&&r<=qr)dep[node].add+=x;
else if(l>qr||r<ql)return;
else add(ls,ql,qr,x),add(rs,ql,qr,x);
}
int qsm(int node,int p)
{
int l=dep[node].l,r=dep[node].r;
if(l==r)return dep[node].add+dep[node].sum;
else if(p<=mid)return qsm(ls,p)+dep[node].add;
else return qsm(rs,p)+dep[node].add;
}
void initdfs(int x,int fa,int nowd)
{
dp[x]=nowd;
trefa[x]=fa;
anc[x][0]=fa;
for(int i=1;i<=20;i++)anc[x][i]=anc[anc[x][i-1]][i-1];
ranks[x]=++nowr;
lranks[x]=rranks[x]=nowr;
for(int i=fst[x];i!=-1;i=nxt[i])
{
if(v[i]==fa)continue;
initdfs(v[i],x,nowd+1);
rranks[x]=max(rranks[x],rranks[v[i]]);
}
add(1,lranks[x],rranks[x],1);
}
int getLCA(int a,int b)
{
if(dp[a]<dp[b])swap(a,b);
for(int i=20;i>=0;i--)
if(dp[anc[a][i]]>=dp[b])
a=anc[a][i];
if(a==b)return a;
for(int i=20;i>=0;i--)
if(anc[a][i]!=anc[b][i])
a=anc[a][i],b=anc[b][i];
return anc[a][0];
}
void comb(int a,int b)
{
int lca=findbel(getLCA(a,b));
int bl=findbel(lca);
a=findbel(a),b=findbel(b);
for(int i=a;i!=bl;i=trefa[i])
{
i=findbel(i);
if(i==bl)break;
add(1,lranks[i],rranks[i],-1);
belong[i]=bl;
}
for(int i=b;i!=bl;i=trefa[i])
{
i=findbel(i);
if(i==bl)break;
add(1,lranks[i],rranks[i],-1);
belong[i]=bl;
}
}
void graphinit()
{
for(int i=1;i<=n;i++)fa[i]=i,belong[i]=i;
for(int i=1;i<=m;i++)
{
if(!isdel.count(make_pair(srcu[i],srcv[i])))
{
if(findfa(srcu[i])!=findfa(srcv[i]))addeg(srcu[i],srcv[i]),addeg(srcv[i],srcu[i]),fa[findfa(srcu[i])]=srcv[i];
else suoa[++suon]=srcu[i],suob[suon]=srcv[i];
}
}
build(1,1,n);
initdfs(1,0,1);
for(int i=1;i<=suon;i++)comb(suoa[i],suob[i]);
}
void input()
{
int a,b,c;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d%d",&srcu[i],&srcv[i]);
while(1)
{
if(!(~scanf("%d%d%d",&c,&a,&b)))break;
if(c==-1)break;
q++;
qur[q].a=a,qur[q].b=b,qur[q].c=c;
if(c==0)isdel.insert(make_pair(a,b)),isdel.insert(make_pair(b,a));
}
}
void work()
{
for(int i=q;i>=1;i--)
{
if(qur[i].c==1)
{
int lca=getLCA(qur[i].a,qur[i].b);
qur[i].ans=qsm(1,ranks[qur[i].a])+qsm(1,ranks[qur[i].b])-2*qsm(1,ranks[lca]);
}
else comb(qur[i].a,qur[i].b);
}
for(int i=1;i<=q;i++)if(qur[i].c==1)printf("%d\n",qur[i].ans);
}
int main()
{
memset(fst,0xff,sizeof(fst));
input();
graphinit();
work();
return 0;
}
0 条评论