自分でも覚えてなかったというのに…。
https://atcoder.jp/contests/yahoo-procon2019-final-open/tasks/yahoo_procon2019_final_b
問題
木を成す2つのグラフが与えられる。
両方の木から1頂点ずつ選び、間に辺を追加してできる木の直径について、全頂点対の組み合わせにおける総和を求めよ。
解法
より難しい問題を過去に解いているので、そちらを参照。
Codeforces #411 Div1 D. Expected diameter of a tree - kmjp's blog
pair<int,int> farthest(vector<vector<int>>& E, int cur,int pre,int d,vector<int>& D) { D[cur]=d; pair<int,int> r={d,cur}; FORR(e,E[cur]) if(e!=pre) r=max(r, farthest(E,e,cur,d+1,D)); return r; } vector<int> diameter(vector<vector<int>>& E) { // diameter,center vector<int> D[3]; D[0].resize(E.size()); D[1].resize(E.size()); auto v1=farthest(E,0,0,0,D[0]); auto v2=farthest(E,v1.second,v1.second,0,D[0]); farthest(E,v2.second,v2.second,0,D[1]); int i; FOR(i,D[0].size()) D[2].push_back(max(D[0][i],D[1][i])); return D[2]; } int N,M; vector<vector<int>> E[2]; vector<int> D[2]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; E[0].resize(N); FOR(i,N-1) { cin>>x>>y; E[0][x-1].push_back(y-1); E[0][y-1].push_back(x-1); } cin>>M; E[1].resize(M); FOR(i,M-1) { cin>>x>>y; E[1][x-1].push_back(y-1); E[1][y-1].push_back(x-1); } D[0]=diameter(E[0]); D[1]=diameter(E[1]); vector<ll> S; S.push_back(0); sort(ALL(D[0])); sort(ALL(D[1])); FORR(d,D[1]) S.push_back(d+S.back()); ll ret=0; ll MD=max(D[0].back(),D[1].back()); FORR(d,D[0]) { int e=MD-d-1; x=lower_bound(ALL(D[1]),e)-D[1].begin(); ret+=MD*x+(S[M]-S[x]+1LL*(d+1)*(M-x)); } cout<<ret<<endl; }
まとめ
書いた本人すら忘れてる過去記事を引っ張ってくる人は何者なんですかね。