Good Bye 2013 : F. New Year Tree

ある特性を知っているか否かで極端に難易度が変わる問題。
http://codeforces.com/contest/379/problem/F

問題

１番の頂点を根とする木があり、初期状態ではそこに２・３・４番の点が接続されている。
この後Q個のクエリが与えられる。
各クエリでは既存の頂点番号vが与えられ、そこに新たな頂点N+1・N+2を接続する(Nはそれまでの頂点数)。

各クエリ処理後の木の直径(最長の頂点間距離)を示せ。

解法

どうもこれは最近別のコンテストで類似した問題が出たようだ。

以下の特性を利用すると簡単に解ける。
「現在の直径が頂点A,B間の距離だった場合、そこに頂点Cを付け加えて直径が伸びる場合、その距離はA,C間またはB,C間のいずれかと等しい」

よって距離が最長の２点を覚えておき、クエリを処理するたびにそれら２点との距離を比較して、距離が長くなりそうなら「最長の２点」を入れ替えていけばよい。
２点間の距離は親子関係をdoublingし、Least Common Ancestorを処理することで頂点数がQに比例するので全体でO(QlogQ)で処理できる。
このテクニックは蟻本でも出てくる。
ついでにdoublingとLCA処理ををライブラリ化しておいた。

ともあれ最初の特性を知らないと簡単に解けないね。

int Q,N;
int depth[1000010];
int pa[21][1<<20];
int dist(int x,int y) {
	int res=0,i;
	if(depth[x]<depth[y]) swap(x,y);
	res = depth[x]-depth[y]; // go same depth
	for(i=19;i>=0;i--) if(res&(1<<i)) x=pa[i][x];
	for(i=19;i>=0;i--) if(pa[i][x]!=pa[i][y]) res += (1<<i)*2,x=pa[i][x],y=pa[i][y];
	return res + 2*(x!=y);
}

void solve() {
	int f,i,j,k,l,x,y;
	int mia,mib,d;
	
	N=4;
	pa[0][1]=0;
	depth[1]=0;
	pa[0][2]=pa[0][3]=pa[0][4]=1;
	depth[2]=depth[3]=depth[4]=1;
	FOR(i,20) for(j=1;j<=N;j++) pa[i+1][j]=pa[i][pa[i][j]];
	
	mia=2,mib=4,d=2;
	
	cin>>Q;
	FOR(j,Q) {
		cin>>x;
		pa[0][N+1] = pa[0][N+2] = x;
		depth[N+1] = depth[N+2] = depth[x]+1;
		FOR(i,20) pa[i+1][N+1]=pa[i][pa[i][N+1]];
		FOR(i,20) pa[i+1][N+2]=pa[i][pa[i][N+2]];
		
		if(dist(mia,N+1)>d) d=dist(mia,N+1),mib=N+1;
		else if(dist(mib,N+1)>d) d=dist(mib,N+1),mia=N+1;
		
		_P("%d\n",d);
		N+=2;
	}
}

まとめ

それにしても、最初の４点とか各クエリで２点追加するあたりはこの問題の解法と全然関係ないな。