【打CF，學(xué)算法——四星級(jí)】CodeForces 455C Civilization (【詳解】并查集+樹的直徑)

【CF簡(jiǎn)介】

提交鏈接：CF 455C

題面：

C. Civilization time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Andrew plays a game called "Civilization". Dima helps him.

The game has n cities and m bidirectional roads. The cities are numbered from 1 to n. Between any pair of cities there either is a single (unique) path, or there is no path at all. A path is such a sequence of distinct citiesv₁,?v₂,?...,?v_k, that there is a road between any contiguous citiesv_i andv_i?+?1 (1?≤?i?<?k). The length of the described path equals to(k?-?1). We assume that two cities lie in the same region if and only if, there is a path connecting these two cities.

During the game events of two types take place:

Andrew asks Dima about the length of the longest path in the region where cityx lies. Andrew asks Dima to merge the region where city x lies with the region where cityy lies. If the cities lie in the same region, then no merging is needed. Otherwise, you need to merge the regions as follows: choose a city from the first region, a city from the second region and connect them by a road so as to minimize the length of the longest path in the resulting region. If there are multiple ways to do so, you are allowed to choose any of them.

Dima finds it hard to execute Andrew's queries, so he asks you to help him. Help Dima.

Input

The first line contains three integers n,m,q (1?≤?n?≤?3·10⁵;0?≤?m?<?n; 1?≤?q?≤?3·10⁵) — the number of cities, the number of the roads we already have and the number of queries, correspondingly.

Each of the following m lines contains two integers,a_i andb_i (a_i?≠?b_i;1?≤?a_i,?b_i?≤?n). These numbers represent the road between citiesa_i andb_i. There can be at most one road between two cities.

Each of the following q lines contains one of the two events in the following format:

1 x_i. It is the request Andrew gives to Dima to find the length of the maximum path in the region that contains cityx_i (1?≤?x_i?≤?n).2 x_iy_i. It is the request Andrew gives to Dima to merge the region that contains cityx_i and the region that contains cityy_i (1?≤?x_i,?y_i?≤?n). Note, thatx_i can be equal toy_i. Output

For each event of the first type print the answer on a separate line.

Examples Input

6?0?6
2?1?2
2?3?4
2?5?6
2?3?2
2?5?3
1?1

Output

4

題意：

??? 題目給出一張圖，圖中原有n個(gè)點(diǎn)，m條邊，且m<n，且兩個(gè)點(diǎn)之間沒有重邊，且兩點(diǎn)之間最多只有一條路徑。后續(xù)有兩種操作，操作一，詢問某節(jié)點(diǎn)所在的聯(lián)通塊上最長(zhǎng)的鏈的長(zhǎng)度。操作二，將兩個(gè)聯(lián)通塊相連，要求相連后形成的聯(lián)通塊的最大長(zhǎng)度盡量小。（如果兩點(diǎn)原就在一個(gè)聯(lián)通塊，就不需要連接了）

解題：

??? 第一次寫求樹的直徑，其實(shí)也不難，首先在一個(gè)聯(lián)通塊上隨意找一個(gè)出發(fā)，求得該點(diǎn)可以到的最遠(yuǎn)點(diǎn)的位置，并從最遠(yuǎn)點(diǎn)反向再進(jìn)行dfs一遍，此時(shí)的最大值就為樹的直徑（樹的直徑指的是樹上最長(zhǎng)的鏈的長(zhǎng)度）。因?yàn)?，任意從樹上某一點(diǎn)出發(fā)，能到的最遠(yuǎn)點(diǎn)一定在樹的直徑上，故可以反向dfs，求得最優(yōu)值。

??? 可以用并查集的方式來維護(hù)節(jié)點(diǎn)的集合關(guān)系。當(dāng)合并兩個(gè)集合時(shí)，為了使合并后得到的樹的直徑最小，會(huì)采取在兩顆樹的直徑的中間點(diǎn)位置相連，這樣就最小化了最長(zhǎng)鏈的優(yōu)勢(shì)，從而滿足了題意，將新得到的聯(lián)通塊合并（更新fa數(shù)組），同時(shí)更新代表節(jié)點(diǎn)對(duì)應(yīng)的val值。

相關(guān)知識(shí)點(diǎn)：

?????? 并查集入門

代碼：

#include#include#include#include#include#include#include#define?maxn?300005
using?namespace?std;
//存儲(chǔ)邊
struct?edge
{
	int?u,v,nxt;
}store[maxn*2];
//cur為當(dāng)前dfs的起點(diǎn)，max_len最大長(zhǎng)度,p最遠(yuǎn)點(diǎn)位置
int?head[maxn],cnt=0,fa[maxn],val[maxn],cur,max_len,p;
//訪問標(biāo)記數(shù)組
bool?vis[maxn];
//添加雙向邊
void?addedge(int?u,int?v)
{
	store[cnt].nxt=head[u];
	head[u]=cnt;
	store[cnt].u=u;
	store[cnt++].v=v;
????store[cnt].nxt=head[v];
	head[v]=cnt;
	store[cnt].v=u;
	store[cnt++].u=v;
}
//dfs求樹的直徑，pre是樹的前驅(qū)節(jié)點(diǎn)，避免回去
//flag在第一次時(shí)不標(biāo)記，第二次反向時(shí)標(biāo)記
void?dfs(int?x,int?pre,int?step,int?flag)
{
	vis[x]=flag;
	fa[x]=cur;
????val[x]=step;
	if(val[x]>max_len)
	{
???????max_len=val[x];
	???p=x;
	}
	for(int?i=head[x];~i;i=store[i].nxt)
	{
		if(store[i].v!=pre&&!vis[store[i].v])
			dfs(store[i].v,store[i].u,step+1,flag);
	}
}
//找出集合代表元素，同時(shí)進(jìn)行路徑壓縮
int?Find(int?x)
{
??return?fa[x]!=x?fa[x]=Find(fa[x]):x;?
}
//合并兩個(gè)集合，并更新最長(zhǎng)鏈長(zhǎng)度
void?Union(int?a,int?b)
{
???int?tmp,ta,tb;
???ta=Find(a);
???tb=Find(b);
???tmp=max((val[ta]+1)/2+(val[tb]+1)/2+1,max(val[ta],val[tb]));
???fa[ta]=tb;
???val[tb]=tmp;
}
int?main()
{
????int?n,m,q,a,b,tmp,op,ta,tb;
	memset(head,-1,sizeof(head));
	memset(vis,0,sizeof(vis));
	cnt=0;
	scanf("%d%d%d",&n,&m,&q);
	//構(gòu)圖
	for(int?i=0;i<m;i++)
	{
		scanf("%d%d",&a,&b);
		addedge(a,b);
	}
	//初始化
	for(int?i=1;i<=n;i++)
		fa[i]=i;
	for(int?i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			cur=i;
			max_len=0;
			p=0;
			dfs(i,-1,0,0);
			//可能該點(diǎn)沒有邊，需注意
			if(p!=0)
????????????dfs(p,-1,0,1);
			val[fa[p]]=max_len;
		}
	}
	//操作
	for(int?i=0;i<q;i++)
	{
???????scanf("%d",&op);
	???if(op==1)
	???{
		???scanf("%d",&a);
		???ta=Find(a);
		???printf("%dn",val[ta]);
	???}
	???else
	???{
		???scanf("%d%d",&a,&b);
		???ta=Find(a);
		???tb=Find(b);
		???if(ta==tb)
			???continue;
		???else
			???Union(a,b);
	???}
	}
	return?0;
}