Codeforces #1022 : Div2 E. Spruce Dispute

ちょっと手間取った。
https://codeforces.com/contest/2108/problem/E

問題

奇数Nに対し、N要素の木が与えられる。
ここから1辺を取り除いて縮約したうえで、残る点を2つずつペアにし、その最短経路の総和を最大化したい。
取り除く辺と、点のペアの一例を示せ。

解法

木の中心に対し、根に対し異なるSubTree内の頂点同士をペアにするとよい。
そのうえで、辺を取り除いた時に、削減される最短経路長の総和が最少となる辺を選ぼう。

int T,N;
vector<pair<int,int>> E[202020];
int col[202020];
vector<int> cand;
int root,u,v,del;

int dfs(int cur,int pre) {
	int C=1;
	FORR2(e,a,E[cur]) if(e!=pre) {
		a=dfs(e,cur);
		C+=a;
	}
	FORR2(e,a,E[cur]) if(e==pre) a=N-C;
	return C;
}

int dfs2(int cur,int pre,int croot,int d) {
	int C=1;
	
	FORR2(e,a,E[cur]) if(e!=pre) C+=dfs2(e,cur,croot,d+1);
	int de=d+C-1;
	if(d&&de<del) {
		del=de;
		root=croot;
		u=pre;
		v=cur;
	}
	return C;
}

void dfs3(int cur,int pre) {
	if(cur!=v) cand.push_back(cur);
	FORR2(e,a,E[cur]) if(e!=pre) dfs3(e,cur);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) E[i].clear();
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back({y-1,0});
			E[y-1].push_back({x-1,0});
		}
		dfs(0,0);
		
		del=1<<30;
		
		FOR(i,N) {
			vector<pair<int,int>> V={{1,0}};
			FORR2(e,a,E[i]) V.push_back({a,e});
			sort(ALL(V));
			if(V.back().first<=N/2) {
				dfs2(i,i,i,0);
			}
			else if(V.back().first-1<=N/2) {
				dfs2(V.back().second,i,i,1);
			}
		}
		cand.clear();
		dfs3(root,root);
		if(u>v) swap(u,v);
		FOR(i,N) col[i]=0;
		FOR(i,N/2) {
			col[cand[i]]=col[cand[i+N/2]]=i+1;
		}
		if(col[min(u,v)]==0) swap(col[min(u,v)],col[max(u,v)]);
		cout<<u+1<<" "<<v+1<<endl;
		FOR(i,N) cout<<col[i]<<" ";
		cout<<endl;
	}
}

まとめ

難しくはないけど実装がちょっとめんどい。