Codeforces #430 Div2 E. Nikita and game

通らないはずのコードが通って妙に良い成績に。
http://codeforces.com/contest/842/problem/E

問題

１頂点から始まり、毎ステップ葉の頂点に接続する形で拡大していく木を成すグラフが与えられる。
各ステップにおいて、その時点の直径の端点になりうる点の数を求めよ。

解法

まず最終形のグラフにおいて、２頂点の距離を高速に求められるよう、LCAを求める前処理をしておこう。
次に、各ステップにおける直径および両端点を一通り求める。
これは、ステップを進めるたびに追加した点について、前のステップの両端点との距離が前のステップの直径を超えるかどうかで容易に判断できる。

一通り直径と端点を求めたら、再度各ステップで追加される頂点を見ていく。
各頂点は、一度直径の端点になりえない点になってしまうと、以後永遠に端点になることはない。
よって二分探索で直径となりうる最後のステップを求めよう。

あとはimos法の要領で各ステップにおいて端点になりうる頂点の数を数え上げる。

int M;
int P[21][300005],D[300005];

int X[303030],Y[303030],dia[303030];
int ret[303030];

int dist(int a,int b) {
	int ret=0,i,aa=a,bb=b;
	if(D[aa]>D[bb]) swap(aa,bb);
	for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb];
	for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb];
	return D[a]+D[b]-2*D[(aa==bb)?aa:P[0][aa]];  // dist
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M;
	FOR(i,M) {
		cin>>P[0][i+1];
		P[0][i+1]--;
		D[i+1]=D[P[0][i+1]]+1;
	}
	FOR(i,19) FOR(x,M+1) P[i+1][x]=P[i][P[i][x]];
	
	X[1]=0;
	Y[1]=dia[1]=1;
	for(i=2;i<=M;i++) {
		X[i]=X[i-1];
		Y[i]=Y[i-1];
		dia[i]=dia[i-1];
		
		if(dist(X[i],i)>dia[i-1]) {
			dia[i]++;
			Y[i]=i;
		}
		else if(dist(Y[i],i)>dia[i-1]) {
			dia[i]++;
			X[i]=i;
		}
	}
	
	FOR(i,M+1) {
		ret[i]++;
		x=i-1;
		for(j=20;j>=0;j--) {
			int tmp=x+(1<<j);
			if(tmp>M) continue;
			if(max(dist(X[tmp],i),dist(Y[tmp],i))==dia[tmp]) x=tmp;
		}
		ret[x+1]--;
	}
	for(i=1;i<=M;i++) {
		ret[i]+=ret[i-1];
		_P("%d\n",ret[i]);
	}
	
}

まとめ

O(step^2)の解法で通ってしまいびっくり。