Codeforces #769 : Div2 E2. Distance Tree

本番Dまではサクサク解いてるけどEで詰まったな…。
https://codeforces.com/contest/1632/problem/E2

問題

N頂点の木を成すグラフを与えられる。
f(x)を以下のように定めるとき、f(1)～f(N)を求めよ。

• 任意の2点間に、1本だけ長さxの辺を加えたときの、根頂点までの最大距離の最小値

解法

辺を加えるなら、根頂点とどこかの葉一択である。
ある頂点Vにおいて、異なる子頂点のSubTreeに属する最も遠い2つの頂点をA,Bとしたとする。Depth(A)≧Depth(B)の時、仮に根とAの間に長さXの辺を張ると、解はmin(Depth(B),Depth(A)+Depth(B)-2*Depth(V)+x)以上である。
よって、この式を各頂点において最大値を取ったものとなる。

int T,N;
vector<int> E[303030];
int dia[303030];

int dfs(int cur,int pre,int d) {
	vector<int> L;
	L.push_back(d);
	L.push_back(d);
	FORR(e,E[cur]) if(e!=pre) {
		L.push_back(dfs(e,cur,d+1));
	}
	sort(ALL(L));
	reverse(ALL(L));
	if(L[1]>0) {
		dia[L[1]-1]=max(dia[L[1]-1],L[0]+L[1]-2*d);
	}
	return L[0];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N+2) {
			E[i].clear();
			dia[i]=0;
		}
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		
		int ma=dfs(0,0,0);
		for(i=N-1;i>=0;i--) dia[i]=max(dia[i],dia[i+1]);
		int cur=0;
		for(i=1;i<=N;i++) {
			while(cur<ma&&(dia[cur]+1)/2+i>cur) cur++;
			cout<<cur<<" ";
		}
		cout<<endl;
	}
}

まとめ

Div2 Eの割に実装は軽い。