これはすんなり解けた。
http://codeforces.com/contest/455/problem/C
問題
初期状態でN個の点があり、M個の辺が張られている。
M個の辺は閉路がないことがわかっている。
ここで以下のクエリQ個に答えよ。
解法
クラスタはUnion-Findで処理していく。
まず最初のM辺分をUnion-Findで連結しつつ、各クラスタの直径を求めておく。
グラフの直径はARC#022 Cで出たとおりDFS2回で求められるので、O(N)で済む。
後は各クエリを処理していく。
1つ目のクエリは計算済みの値を返すだけなので、2つ目のクエリでうまく計算が必要。
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の方が簡単だった。