方針は難しくないんだけど、手間がかかりすぎる…。
https://atcoder.jp/contests/ddcc2020-final/tasks/ddcc2020_final_d
問題
N点N辺の無向連結グラフが与えられる。
各辺には長さが設定されている。
各辺が取り除かれた状態における、連結成分内の2点間の最短路の最長の長さを答えよ。
解法
いわゆるなもりグラフなので、閉路と閉路上の各点から閉路外に伸びた木(Editorial中では苗と表現している)に分離しよう。
まず、個々の苗について閉路上の点を根として木DPし、各点から最深点までの距離とsubtree内の最長パス長を求めよう。
次に、他の苗との間の距離を考える。
その際、閉路の各点をnodeとしてSegTreeを構築する。閉路を切り開いて3周分ほど取っておくとよい。
閉路1周の長さをKとして、各ノードには以下を乗せる。
- ノードの区間に対応する閉路上の開始位置と終了位置
- 同区間において閉路左端の点からの最遠点までの距離と、その点がある苗の番号
- 同区間において閉路右端の点からの最遠点までの距離と、その点がある苗の番号
- 同区間内における最長パスと、その両端点がある苗の番号
これらは容易に合成できる。
さて、最初のSubtreeの処理は親方向の辺を処理していないので、全方位木DPの処理を行う必要があるが、それには各苗の根に対して以下を求めておく必要がある。
- その苗の根から他の苗の最遠点までの最長距離
- 他の苗同士で構築されるパスの最長値
前者は先ほどのSegTreeで容易にとれる。閉路上左回りした方が近い苗と、右回りした方が近い苗の間で上記SegTreeを用いればよい。
最後だが、元のグラフにおいて最長パスを成す端点を保持する苗がx,yとする。
その場合、x,y以外の苗を考えるときは、元のグラフの最長パスが当然最長なので、その場合何もしなくてよい。
x,yの苗については、x,yをそれぞれ取り除いた時のSegTreeを再構築して最長パスを求める。
親方向の最遠点と最長パスがわかれば、あとは全方位木DPの要領で各点に書き戻すだけ。
int N,LS; int A[202020],B[202020],C[202020]; vector<vector<int>> E[202020]; set<int> ES[202020]; int in[202020]; int id[202020]; vector<int> V; vector<ll> D; ll L; vector<ll> MD[202020],MP[202020]; ll PD[202020],PP[202020],BP[202020]; ll DD[202020]; struct node { ll L,R; ll ML,MR,MP; int Lid,Rid,Pid[2]; }; template<class V,int NV> class SegTree_1 { public: vector<V> val; V comp(V l,V r){ if(l.L==-1) return r; if(r.L==-1) return l; V node; node.L=l.L; node.R=r.R; node.MP=max({l.MP,r.MP,l.MR+r.ML+r.L-l.R}); if(node.MP==l.MP) { node.Pid[0]=l.Pid[0]; node.Pid[1]=l.Pid[1]; } else if(node.MP==r.MP) { node.Pid[0]=r.Pid[0]; node.Pid[1]=r.Pid[1]; } else { node.Pid[0]=l.Rid; node.Pid[1]=r.Lid; } if(l.ML>r.ML+r.L-l.L) { node.ML=l.ML; node.Lid=l.Lid; } else { node.ML=r.ML+r.L-l.L; node.Lid=r.Lid; } if(l.MR+r.R-l.R>r.MR) { node.MR=l.MR+r.R-l.R; node.Rid=l.Rid; } else { node.MR=r.MR; node.Rid=r.Rid; } return node; }; SegTree_1(){val=vector<V>(NV*2);FORR(v,val) v.L=-1;} V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y if(r<=x || y<=l) return {.L=-1}; if(x<=l && r<=y) return val[k]; return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1)); } void update(int entry, V v) { entry += NV; val[entry]=v; //上書きかチェック while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]); } }; SegTree_1<node,1<<20> st; void dfs(int cur,int pre,int oid,ll d) { if(cur==oid && d) { L=d; return; } id[cur]=V.size(); V.push_back(cur); D.push_back(d); FORR(e,E[cur]) if(id[e[0]]==-2 || (e[0]==oid&&id[cur]>=2)) dfs(e[0],cur,oid,d+e[2]); } void dfs2(int cur,int pre,ll d) { MD[cur].push_back(0); MD[cur].push_back(0); DD[cur]=d; FORR(e,E[cur]) if(id[e[0]]==-1 && e[0]!=pre) { dfs2(e[0],cur,d+e[2]); MP[cur].push_back(BP[e[0]]); MD[cur].push_back(MD[e[0]][0]+e[2]); } sort(ALL(MD[cur])); reverse(ALL(MD[cur])); sort(ALL(MP[cur])); reverse(ALL(MP[cur])); BP[cur]=MD[cur][0]+MD[cur][1]; if(MP[cur].size()) BP[cur]=max(BP[cur],MP[cur][0]); } void dfs3(int cur,int pre,ll md, ll mp) { PP[cur]=mp; PD[cur]=md; FORR(e,E[cur]) if(id[e[0]]==-1 && e[0]!=pre) { ll nmd=max(md,((MD[cur][0]==MD[e[0]][0]+e[2])?MD[cur][1]:MD[cur][0]))+e[2]; ll nmp=0; if(MD[cur][0]==MD[e[0]][0]+e[2]){ nmp=MD[cur][1]+MD[cur][2]+md-min({MD[cur][1],MD[cur][2],md}); } else if(MD[cur][1]==MD[e[0]][0]+e[2]){ nmp=MD[cur][0]+MD[cur][2]+md-min({MD[cur][0],MD[cur][2],md}); } else { nmp=MD[cur][0]+MD[cur][1]+md-min({MD[cur][0],MD[cur][1],md}); } nmp=max(nmp,mp); if(MP[cur][0]==BP[e[0]]) { if(MP[cur].size()>=2) nmp=max(nmp,MP[cur][1]); } else nmp=max(nmp,MP[cur][0]); dfs3(e[0],cur,nmd,nmp); } } void setsegtree(int i,bool init=true) { node n; n.L=n.R=D[i]; n.Lid=n.Rid=n.Pid[0]=n.Pid[1]=i; if(init) { n.ML=n.MR=MD[V[i]][0]; n.MP=BP[V[i]]; } else { n.ML=n.MR=n.MP=-1LL<<60; } st.update(i,n); } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>A[i]>>B[i]>>C[i]; A[i]--; B[i]--; E[A[i]].push_back({B[i],i,C[i]}); E[B[i]].push_back({A[i],i,C[i]}); ES[A[i]].insert(B[i]); ES[B[i]].insert(A[i]); in[A[i]]++; in[B[i]]++; } queue<int> Q; FOR(i,N) { id[i]=-2; if(in[i]==1) Q.push(i); } while(Q.size()) { x=Q.front(); Q.pop(); id[x]=-1; FORR(e,ES[x]) { ES[e].erase(x); in[e]--; if(in[e]==1) Q.push(e); } } FOR(i,N) if(id[i]==-2) { dfs(i,i,i,0); break; } FOR(i,N) if(id[i]>=0) dfs2(i,i,0); LS=V.size(); FOR(i,2*LS) V.push_back(V[i%LS]); FOR(i,LS) D.push_back(D[i]+L); FOR(i,LS) D.push_back(D[i]+2*L); FOR(i,3*LS) setsegtree(i); //半周ずつ回す vector<vector<ll>> ring; FOR(i,3) { int LL=0,RR=0; node NT; NT.MP=-1; FOR(LL,LS) { while(D[RR]-D[LL]<=L/2) RR++; node NL=st.getval(LL,RR); if(NL.MP>NT.MP) NT=NL; } for(LL=RR=2*LS-1;RR>=LS;RR--) { while(D[RR]-D[LL]<=L/2) LL--; node NL=st.getval(LL+1,RR+1); if(NL.MP>NT.MP) NT=NL; } ring.push_back({NT.MP,NT.Pid[0]%LS,NT.Pid[1]%LS}); if(i==0) { x=NT.Pid[0]%LS; y=NT.Pid[1]%LS; ring.push_back({NT.MP,x,y}); setsegtree(x,false); setsegtree(x+LS,false); setsegtree(x+LS*2,false); } else if(i==1) { setsegtree(x); setsegtree(x+LS); setsegtree(x+LS*2); setsegtree(y,false); setsegtree(y+LS,false); setsegtree(y+LS*2,false); } else { setsegtree(y); setsegtree(y+LS); setsegtree(y+LS*2); } } sort(ALL(ring)); reverse(ALL(ring)); FOR(i,LS) { x=lower_bound(ALL(D),D[i+LS]+(L+1)/2)-D.begin(); node NL=st.getval(x-LS,i+LS); node NR=st.getval(i+LS+1,x); ll md=0,mp=0; if(NL.L>=0) { md=max(md,(D[i+LS]-NL.R)+NL.MR); mp=max({mp,NL.MP}); } if(NR.L>=0) { md=max(md,NR.L-D[i+LS]+NR.ML); mp=max(mp,NR.MP); } //関係ないところのmd FORR(r,ring) { if(r[1]!=i&&r[2]!=i) { mp=max(mp,r[0]); break; } } dfs3(V[i],V[i],md,mp); } FOR(i,N) { if(id[A[i]]>=0 && id[B[i]]>=0) { x=id[A[i]]; y=id[B[i]]; if(x>y) swap(x,y); if(x+1<y) x--; auto n=st.getval(x+1,x+LS+1); cout<<n.MP<<endl; } else { x=A[i]; y=B[i]; if(DD[x]>DD[y]) swap(x,y); ll mp=PP[x]; if(MP[y].size()) mp=max(mp,MP[y][0]); mp=max(mp,MD[y][0]+MD[y][1]); mp=max(mp,MP[x][0]); vector<ll> T; FOR(j,min(3,(int)MD[x].size())) T.push_back(MD[x][j]); T.push_back(PD[x]); T.push_back(0); T.push_back(0); sort(ALL(T)); reverse(ALL(T)); if(T[0]==MD[y][0]+C[i]) { mp=max(mp,T[1]+T[2]); } else if(T[1]==MD[y][0]+C[i]) { mp=max(mp,T[0]+T[2]); } else { mp=max(mp,T[0]+T[1]); } cout<<mp<<endl; } } }
まとめ
AtCoderのACコードで最長になってしまいかなり疲れた。
ただ前最長のARC022Dスプリンクラーは幾何問題で精度にも気を使う必要があったので、それよりはマシ。