Codeforces #507 Div1 D. You Are Given a Tree

このテクは覚えておかなければ…。
http://codeforces.com/contest/1039/problem/D

問題

N頂点の木を成すグラフが与えられる。
以下のf(i)について、f(1)～f(N)を列挙せよ。
f(i) := 木から互いに頂点・辺を共有しない長さiのパスが最大何本とれるか

解法

iが決まっているとき、f(i)はO(N)で求められる。
これは子要素にある長さiに満たないパス長の上位２位までを管理する定番DPである。
ただこれをN回行うと当然間に合わない。

ここで、f(i)は以下の特性がある。

• f(i) ≦ N/i
• f(i)は単調減少

f(√N)～f(N)の間は高々(√N+1)通りの値しかありえないので、同じ値が連続して多数現れるはず。
そこで二分探索による解法を考える。
f(L)とf(R)が確定しているとき、f(L)～f(R)の間を埋めよう。

• f(L)=f(R)ならf(L)～f(R)は皆同じ値。
• f(L)!=f(R)ならM=(L+R)/2についてf(M)を求め、以後f(L)～f(M)とf(M)～f(R)を再帰的に埋めていく。

int N;
vector<int> E[101010],V2;
int D[101010];
vector<pair<int,int>> V;
int ret[101010];
int cand[101010][2];

void dfs(int cur,int pre,int depth) {
	D[cur]=depth;
	V.push_back({depth,cur});
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur,depth+1);
}

int num(int d) {
	int ret=0;
	
	FORR(v,V) {
		int cur=v.second;
		cand[cur][0]=cand[cur][1]=0;
		FORR(e,E[cur]) if(D[e]>D[cur] && cand[e][0]>=0) {
			int c=cand[e][0];
			if(c>=cand[cur][0]) {
				cand[cur][1]=cand[cur][0];
				cand[cur][0]=c;
			}
			else cand[cur][1]=max(cand[cur][1],c);
		}
		
		if(cand[cur][0]+cand[cur][1]+1>=d) {
			ret++;
			cand[cur][0]=-1;
		}
		else {
			cand[cur][0]++;
		}
	}
	return ret;
}

void dfs2(int L,int R) {
	if(L+1>=R) return;
	if(ret[L]==ret[R]) {
		for(int i=L+1;i<R;i++) ret[i]=ret[L];
		return;
	}
	int M=(L+R)/2;
	ret[M]=num(M);
	dfs2(L,M);
	dfs2(M,R);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0,0,0);
	sort(ALL(V));
	reverse(ALL(V));
	
	ret[1]=N;
	ret[N]=num(N);
	dfs2(1,N);
	for(i=1;i<=N;i++) cout<<ret[i]<<endl;
}

まとめ

割と定数倍が重いので注意。