最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

热资讯！Codeforces 1763 F Edge Queries 题解

来源：博客园


【资料图】

题目链接

先观察满足题目中给出的限制的图有什么特点。先看\(C_u\)，它指的是所有与\(u\)在同一个简单环内的节点。发现一个点v在\(C_u\)中，当且仅当\(u,v\)点双连通。关于点双连通的判断。首先必要性是显然的，不点双连通显然不行。至于充分性，可以把\(u\)作为根跑出dfs树，根据上面点双连通的判断方法，此时u和v之间的树上路径中的每一个点一定至少有1条非树边"跨过"(除了u和v)。至于跨过的定义，下图中左边的红点被跨过了，而右边的没有。

然后，u和v在一个简单环中等价于：以u为原点、v为汇点，每条边能双向走、容量为1，此时u到v的最大流\(\ge 2\)。由于最大流等于最小割，证明最小割\(\ge 2\)即可。很容易发现不可能只割掉1条边使uv不连通，所以原命题得证。

那么\(S_u=C_u\)又说明什么呢？再来看看上面链接里判断点双连通的方法，其中有些树边被加进了同一个连通块中，不妨看成把一些树边染成了相同的颜色，没有非树边跨过的边没有被染颜色，则所有同色边连接的所有点是属于同一个点双连通分量的。这题中\(S_u=C_u\)其实说明了不能有一个点同时属于两个点双连通分量，也就是不能有两条都被染色但颜色不同的树边挨在一起。如果一个点u同时属于两个分量，那显然这两个分量中所有的点都在\(C_u\)中，但无法找到一个很长的简单环同时包括这两个分量的所有点。所以这就说明了输入的图长这样：一些由同色边连成的点双连通分量，之间用树边(同时也是桥边)连成一棵树。在这种情况下，点双分量和边双分量是一样的，边双比较好写，所以可以用边双的方法来把所有分量处理出来。

现在处理出所有的分量了，来看回答询问。首先u和v之间的原图桥边肯定是不能删的。把每个分量看成一个点建一棵新树，令U表示u所在的分量缩成的点，V同理。则U~V路径上某一些点代表的分量中的所有边能被删掉。对于路径中间一个不是U也不是V的点，它代表的分量中的边能被删取决于：

对于端点U和V的分量来说也是一样的，但是需要分类讨论。统计答案维护每个点到根的和就行了，询问的时候求一下LCA，然后相减。维护的时候细节比较多，但是都不难想。

时间复杂度\(O(nlogn)\)。

点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;int n,m,add[200010],dep[200010];vector  e,g[200010],tg[200010];bool vis[200010],isBri[200010];void dfs(int pos,int par){  vis[pos]=true;  rep(i,g[pos].size()) if(g[pos][i].fi!=par)  {    if(!vis[g[pos][i].fi]) tg[pos].pb(g[pos][i]),dep[g[pos][i].fi]=dep[pos]+1,dfs(g[pos][i].fi,pos);    else if(dep[g[pos][i].fi]-1) isBri[lst]=true;}int fa[200010],ecnt[200010];vector  v[200010];int Find(int x){return fa[x]==x ? x:fa[x]=Find(fa[x]);}vector  > ng[200010];int root,dep2[200010],fa2[200010][23],sum[200010];map  consum;pii fae[200010];void dfs3(int pos,int par,int dd,int becon=-1){  dep2[pos]=dd;fa2[pos][0]=par;  rep(i,ng[pos].size()) if(ng[pos][i].fi!=par)  {    sum[ng[pos][i].fi]=sum[pos];    if(becon!=-1&&becon!=ng[pos][i].se.fi) sum[ng[pos][i].fi]+=ecnt[pos];    dfs3(ng[pos][i].fi,pos,dd+1,ng[pos][i].se.se);  }  else fae[pos]=ng[pos][i].se;}int getLCA(int x,int y){  for(int i=19;i>=0;--i) if(fa2[x][i]>0&&dep2[fa2[x][i]]>=dep2[y]) x=fa2[x][i];  for(int i=19;i>=0;--i) if(fa2[y][i]>0&&dep2[fa2[y][i]]>=dep2[x]) y=fa2[y][i];  if(x==y) return x;  for(int i=19;i>=0;--i) if(fa2[x][i]!=fa2[y][i]) x=fa2[x][i],y=fa2[y][i];  return fa2[x][0];}int getFa(int x,int y){  for(int i=19;i>=0;--i) if(y&(1<>n>>m;  int x,y;  rep(i,m)  {    scanf("%d%d",&x,&y);    g[x].pb(mpr(y,i));g[y].pb(mpr(x,i));    e.pb(mpr(x,y));  }  dfs(1,0);  dfs2(1);  repn(i,n) fa[i]=i;  rep(i,m) if(!isBri[i])  {    ++ecnt[e[i].fi];++ecnt[e[i].se];    if(Find(e[i].fi)!=Find(e[i].se)) fa[Find(e[i].fi)]=Find(e[i].se);  }  repn(i,n) v[Find(i)].pb(i);  repn(i,n) if(v[i].size()) rep(j,v[i].size()) if(v[i][j]!=i) ecnt[i]+=ecnt[v[i][j]];  rep(i,m) if(isBri[i])  {    x=Find(e[i].fi);y=Find(e[i].se);    ng[x].pb(mpr(y,e[i]));ng[y].pb(mpr(x,mpr(e[i].se,e[i].fi)));    consum[mpr(x,y)]=consum[mpr(y,x)]=e[i].fi+e[i].se;  }  root=Find(1);  dfs3(root,0,0);  rep(i,20) repn(j,n) fa2[j][i+1]=fa2[fa2[j][i]][i];  int q;  cin>>q;  rep(qn,q)  {    scanf("%d%d",&x,&y);    if(x==y)    {      puts("0");      continue;    }    int xx=x,yy=y;    x=Find(x);y=Find(y);    if(x==y)    {      printf("%d\n",ecnt[x]/2);      continue;    }    if(dep2[x]>dep2[y]) swap(x,y),swap(xx,yy);    int lca=getLCA(x,y);    if(lca==x)    {      int nlca=getFa(y,dep2[y]-dep2[x]-1);      int ans=sum[y]-sum[nlca];      if(fae[y].fi!=yy) ans+=ecnt[y];      if(fae[nlca].se!=xx) ans+=ecnt[x];      printf("%d\n",ans/2);    }    else    {      int xlca=getFa(x,dep2[x]-dep2[lca]-1),ylca=getFa(y,dep2[y]-dep2[lca]-1);      int ans=sum[x]+sum[y]-sum[xlca]-sum[ylca];      if(fae[xlca].se!=fae[ylca].se) ans+=ecnt[lca];      if(fae[x].fi!=xx) ans+=ecnt[x];      if(fae[y].fi!=yy) ans+=ecnt[y];      printf("%d\n",ans/2);    }  }  termin();}

关键词： 当且仅当 时间复杂度 找到一个