割とすんなり。
https://atcoder.jp/contests/past202104-open/tasks/past202104_o
問題
N点M辺の連結無向グラフが与えられる。
なお、M≦N+10である。
クエリとして2点が与えられるので、その間の最短距離を求めよ。
解法
Mが小さいことを利用する。
まず適当な全域木を求め、それらをLCAで高速に距離計算できるようにしておく。
ここで、全域木に使わなかった(M-(N-1))辺の端点について、そこから各点までの最短距離を求めておこう。
各クエリの処理は、上記各端点ついて、その端点を経由した場合を総当たりしつつ、端点を通らない場合と比較して最小値を答えよう。
template<int um> class UF { public: vector<int> par,rank,cnt; UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;} void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;} int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));} int count(int x) { return cnt[operator[](x)];} int operator()(int x,int y) { if((x=operator[](x))==(y=operator[](y))) return x; cnt[y]=cnt[x]=cnt[x]+cnt[y]; if(rank[x]>rank[y]) return par[x]=y; rank[x]+=rank[x]==rank[y]; return par[y]=x; } }; UF<101010> uf; int N,M; vector<int> E[101010],E2[101010]; vector<int> cand; int DD[101010][21]; int P[21][200005],D[200005]; void dfs(int cur) { FORR(e,E[cur]) if(e!=P[0][cur]) D[e]=D[cur]+1, P[0][e]=cur, dfs(e); } int getpar(int cur,int up) { int i; FOR(i,20) if(up&(1<<i)) cur=P[i][cur]; return cur; } int lca(int a,int b) { int ret=0,i,aa=a,bb=b; if(D[aa]>D[bb]) swap(aa,bb); for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb]; for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb]; return (aa==bb)?aa:P[0][aa]; // vertex } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,M) { cin>>x>>y; x--,y--; if(uf[x]!=uf[y]) { E[x].push_back(y); E[y].push_back(x); E2[x].push_back(y); E2[y].push_back(x); uf(x,y); } else { E2[x].push_back(y); E2[y].push_back(x); cand.push_back(x); } } FOR(i,cand.size()) { x=cand[i]; FOR(j,N) DD[j][i]=1<<30; queue<int> Q; DD[x][i]=0; Q.push(x); while(Q.size()) { int cur=Q.front(); Q.pop(); FORR(e,E2[cur]) if(DD[e][i]>DD[cur][i]+1) { DD[e][i]=DD[cur][i]+1; Q.push(e); } } } dfs(0); FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]]; int Q; cin>>Q; while(Q--) { cin>>x>>y; x--,y--; int ret=1<<20; FOR(i,cand.size()) ret=min(ret,DD[x][i]+DD[y][i]); int lc=lca(x,y); ret=min(ret,D[x]+D[y]-2*D[lc]); cout<<ret<<endl; } }
まとめ
辺に距離がついてもよいかと思ったけど、この問題では距離無しだった。