Codeforces #260 Div1 C. Civilization

これはすんなり解けた。
http://codeforces.com/contest/455/problem/C

問題

初期状態でN個の点があり、M個の辺が張られている。
M個の辺は閉路がないことがわかっている。

ここで以下のクエリQ個に答えよ。

1. 点xを含むクラスタの直径を答える。
2. 点xを含むクラスタと点yを含むクラスタを１辺を追加して連結する。この際、連結後のグラフの直径が最短となるように辺を張る。

解法

クラスタはUnion-Findで処理していく。
まず最初のM辺分をUnion-Findで連結しつつ、各クラスタの直径を求めておく。
グラフの直径はARC#022 Cで出たとおりDFS2回で求められるので、O(N)で済む。

後は各クエリを処理していく。
１つ目のクエリは計算済みの値を返すだけなので、２つ目のクエリでうまく計算が必要。
xを含むクラスタの直径をD[x]、yを含むクラスタの直径をD[y]とすると、直径が最短となる連結は両者の重心同士を連結した(D[x]+1)/2+(D[y]+1)/2+1か、元のD[x]・D[y]のうちの最大値となる。

int N,M,Q;
vector<int> E[300001];
int dist[300001];
class UF {
	public:
	static const int ufmax=400002;
	int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	int count(int x) {return ufcnt[x];}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};
UF uf;

int ma,id;
void dfs(int cur,int pre,int d) {
	int i;
	if(d>ma) ma=d,id=cur;
	FOR(i,E[cur].size()) {
		int tar=E[cur][i];
		if(tar==pre) continue;
		dfs(tar,cur,d+1);
	}
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>Q;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		uf.unite(x,y);
		E[x].push_back(y);
		E[y].push_back(x);
	}
	
	FOR(i,N) if(uf[i]==i) {
		ma=0;
		id=i;
		dfs(i,-1,0);
		ma=0;
		dfs(id,-1,0);
		dist[i]=ma;
	}
	while(Q--) {
		cin >> i >> x;
		x=uf[x-1];
		if(i==1) {
			cout << dist[x] << endl;
		}
		else {
			cin>>y;
			y=uf[y-1];
			if(x==y) continue;
			int ax=dist[x],ay=dist[y];
			uf.unite(x,y);
			dist[uf[x]]=max(max(ax,ay),(ax+1)/2+(ay+1)/2+1);
		}
		
	}
}

まとめ

BよりCの方が簡単だった。