このテクは知らなかった。
https://yukicoder.me/problems/no/2296
問題
N頂点の森を成す無向グラフを考える。初期状態で辺はない。
ここに重み付きの辺を加えて行くとする。
2点u,vの距離は、u-v間のパスにおける辺の重みの総和とする。
以下のクエリに順次答えよ。
- 指定された2点間を指定の重みの辺でつなぐ。
- 指定の2点間の距離を求める。
- 1点指定されるので、その点が含まれる連結成分において、全点間の距離のうち最大値を求める。
解法
2点間距離は、連結成分内でLCAを計算できれば容易に求めることができる。
マージテクの要領で成分を連結していく際、大きな連結成分に小さな連結成分の各頂点を追加していく際、LCA計算のためのダブリングを行っていくとよい。
3つ目のクエリについては、連結後の直径を成す2頂点対は、連結前の直径を成す計4頂点のうち2つとなるので、それらの間の距離を総当たりで求めればよい。
int N,Q; ll X; vector<pair<int,int>> E[200005]; int P[21][200005],D[200005]; ll LD[202020]; int V[202020]; pair<int,int> DM[202020]; void dfs(int cur,int pre,int d,ll ld) { P[0][cur]=pre; D[cur]=d; LD[cur]=ld; int i; FOR(i,20) P[i+1][cur]=P[i][P[i][cur]]; FORR2(e,c,E[cur]) if(e!=pre) dfs(e,cur,d+1,ld+c); } 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 } int getroot(int x) { return P[20][x]; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>X>>Q; FOR(i,N) { V[i]=1; DM[i]={i,i}; FOR(j,21) P[j][i]=i; } while(Q--) { cin>>i; if(i==1) { cin>>x>>y; i=X; j=x; if(V[getroot(i)]<V[getroot(j)]) { swap(i,j); } V[getroot(i)]+=V[getroot(j)]; int oj=getroot(j); dfs(j,i,D[i]+1,LD[i]+y); E[i].push_back({j,y}); E[j].push_back({i,y}); i=getroot(i); j=oj; vector<int> V={DM[i].first,DM[i].second,DM[j].first,DM[j].second}; ll md=-1; FORR(v,V) FORR(w,V) if(v<w) { ll lc=lca(v,w); ll ret=LD[v]+LD[w]-2*LD[lc]; if(ret>md) { md=ret; DM[i]={v,w}; } } } else if(i==2) { cin>>x>>y; if(getroot(x)!=getroot(y)) { cout<<-1<<endl; } else { ll lc=lca(x,y); ll ret=LD[x]+LD[y]-2*LD[lc]; cout<<ret<<endl; X=(X+ret)%N; } } else if(i==3) { cin>>x; i=getroot(x); x=DM[i].first; y=DM[i].second; ll lc=lca(x,y); ll ret=LD[x]+LD[y]-2*LD[lc]; cout<<ret<<endl; } else { cin>>x; X=(X+x)%N; } } }
まとめ
LCAのテーブルを更新掛けて行くの初めて。