Codeforces #268 Div1 D. Tree

面白いパートよりつまらないパートの方が実装がめんどい。
http://codeforces.com/contest/468/problem/D

問題

N頂点からなる木が与えられる。
各辺は距離付の無向辺である。

頂点x,y間の最短距離をd(x,y)と表記する。
木の頂点番号を1～Nとするとき、が最大となる、1～Nのpermutation P[i]を答えよ。
最大値となるP[i]の候補が複数あるなら、辞書順最小のものを答えよ。

解法

根をuとすると、d(i,P[i])=d(u,i)+d(u,P[i])-2*d(u,LCA(i,P[i]) )である。
これを各iに対して和を取ると、permutation分がうまく消えてとなる。
この値を最大化するには、後者のLCA(i,P[i])==uとなるようにすれば最後の項が0になり、それにはuとしてグラフの重心を選べばよい。
重心であればP[i]を考慮しなくてよくなり、回答が容易になる。

よって、まず２回DFSを行い、重心となりうる頂点uのうち、が最大となるものを求めればよい。

ここまで前半パートはPermutationと木の特性を元にした割と面白いパート。
面倒なのは辞書順最小のP[i]を求める部分。

iに対応するP[i]として、uにおける異なるsubtreeの頂点を選択していかなければならない。
基本的には二部マッチングを取るだけだが、辞書順最小を満たす取り方をする必要がある。
EditorialはSegTreeを使っているが、自分は別解法で解いた。

各subtreeに含まれる集合を準備する。
さらに各subtreeのうち最小の番号からなる集合(indord)と、各subtree内の残り要素数からなる集合(numord)の２つを取っておく。

辞書順最小の定番として、iを小さい順にP[i]を定めていく。

• 残り要素数が過半数となる集合ができてしまうと、二部マッチングが成立しなくなるので、そのような可能性がある場合、過半数となる集合のうち最小の頂点番号をP[i]にする。
• そうでない場合、残された最小の頂点番号をP[i]にする。ただしP[i]とiが同じsubtreeに含まれそうなら、他の集合の最小頂点番号を持ってくる。

int N,cent;
vector<pair<int,ll> > E[100001];
ll num[100001];
ll sc1[100001],sc2[100001],msc;

int M[100001];
int snum[100001];
vector<vector<int> > SS;
set<int> idord;
map<int,set<int> > numord;


void dfs1(int cur,int pre) {
	int i;
	num[cur]=1;
	FOR(i,E[cur].size()) {
		int tar=E[cur][i].first;
		if(tar!=pre) {
			dfs1(tar,cur);
			sc1[cur]+=sc1[tar]+num[tar]*E[cur][i].second;
			num[cur]+=num[tar];
		}
	}
}
void dfs2(int cur,int pre,ll csc) {
	int i;
	FOR(i,E[cur].size()) {
		int tar=E[cur][i].first;
		if(tar!=pre) dfs2(tar,cur,csc+sc1[cur]+(N-2*num[tar])*E[cur][i].second-sc1[tar]);
	}
	
	ll mav=N-num[cur];
	FOR(i,E[cur].size()) if(E[cur][i].first!=pre) mav=max(mav,num[E[cur][i].first]);
	if(mav<=N/2 && csc+sc1[cur]>msc) msc=csc+sc1[cur], cent=cur;
}
void dfs3(int cur,int pre,int id) {
	int i;
	M[cur]=id;
	FOR(i,E[cur].size()) if(E[cur][i].first != pre) dfs3(E[cur][i].first,cur,id);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y>>j;
		E[x-1].push_back(make_pair(y-1,j));
		E[y-1].push_back(make_pair(x-1,j));
	}
	dfs1(0,-1);
	dfs2(0,-1,0);
	
	_P("%lld\n",2*msc);
	
	M[cent]=0;
	FOR(i,E[cent].size()) dfs3(E[cent][i].first,cent,i+1);
	SS.resize(E[cent].size()+1);
	
	for(i=N-1;i>=0;i--) SS[M[i]].push_back(i);
	FOR(j,SS.size()) snum[j]=SS[j].size()*2, idord.insert(SS[j].back()), numord[-snum[j]].insert(j);
	FOR(i,N) {
		//del old
		j=M[i];
		numord[-snum[j]].erase(j);
		if(numord[-snum[j]].empty()) numord.erase(-snum[j]);
		snum[j]--;
		if(SS[j].size()) numord[-snum[j]].insert(j);
		
		if(-numord.begin()->first>=(N-i) && *numord.begin()->second.begin()!=0) j=*numord.begin()->second.begin(); //largest
		else { //lexico lowest
			ITR(it,idord) if(M[*it]!=j || j==0) {
				j=M[*it];
				break;
			}
		}
		_P("%d ",SS[j].back()+1);
		//del
		numord[-snum[j]].erase(j);
		if(numord[-snum[j]].empty()) numord.erase(-snum[j]);
		idord.erase(SS[j].back());
		SS[j].pop_back();
		snum[j]--;
		if(SS[j].size()) idord.insert(SS[j].back()), numord[-snum[j]].insert(j);
	}
	_P("\n");
}

まとめ

重心求めるところまでは面白いんだけど…ってのはCodeforcesのコメントでも書かれているな。