CF456E
Codeforces Round #260 (Div. 1) C
Codeforces Round #260 (Div. 2) E
http://codeforces.com/contest/455/problem/C
|
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 cities v1, v2, ..., vk, that there is a road between any contiguous cities vi and vi + 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:
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·105; 0 ≤ m < n; 1 ≤ q ≤ 3·105) — 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, ai and bi (ai ≠ bi; 1 ≤ ai, bi ≤ n). These numbers represent the road between cities ai and bi. 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:
Output
For each event of the first type print the answer on a separate line. Sample test(s)
Input
6 0 6 Output
4 |
题意：
给出N个点，M条边，组成无环图（树），给出Q个操作，操作有两种：
1 x ，输出x所在的联通块的最长路；
2 x y ，若x和y在同一联通块，则不操作；若不在同一联通块，则选择这两个联通块的各一个城市连一条边，使新的联通块的最长路最短，若有多种选择则随便选。
题解：
并查集+树的直径
我是看http://blog.csdn.net/keshuai19940722/article/details/38455333的碉炸题解学会的，简直碉炸。
这题认真看其实不难，只是我当时太怂了没看……
首先我们根据初始的边用求树的直径的方法求出每块的最长路，方法就是两遍dfs，第一遍找距离起点最远的点x，这个x肯定是最长路的一端，然后我们从x再dfs一遍，得到最长路md[x]，顺便把整个块的father设为x。
然后操作一就很容易实现，主要是操作二。操作二其实不用真的去连那条边，只要心中有那条边就行，因为连起来后其实主要我们也只看每个块最长路md[x]，其他信息都不用管。设两个块的祖先为fx，fy，设fx的最长路不小于fy的最长路，则我们要把fy的father设为fx，然后更新md[fx]。这个厉害了，我们只要一个超碉的式子就能得到新的md[fx]：
md[fx]=max(md[fx], (md[fx]+)/ + (md[fy]+)/ + );
就是把[x块的最长路的中间点]连接[y块的最长路的中间点]，得到的新路的长度是(x块最长路的一半)加上(y块最长路的一半)加上1。
怪不得天梯第一的tourist大神能十多分钟做出来，果然水，不要不服！只是我们比题还水，一下看不出来这样做…
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define usint unsigned int
#define mz(array) memset(array, 0, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("1biao.out","w",stdout) const int maxn=; struct EDGE{
int v,next;
}e[maxn<<];
int head[maxn],en;
int f[maxn],md[maxn];
int n,m,q;
int maxd,maxi,thefather;
void add(int x,int y){
e[en].v=y;
e[en].next=head[x];
head[x]=en++;
} int getfather(int x){
return f[x]==x ? x:f[x]=getfather(f[x]);
} void link(int x,int y){
int fx,fy;
fx=getfather(x);
fy=getfather(y);
if(fx==fy)return;
if(md[fx]<md[fy])swap(fx,fy);
md[fx]=max(md[fx], (md[fx]+)/ + (md[fy]+)/ + );
f[fy]=fx;
} void dfs(int x,int prex,int step){
f[x]=thefather;
if(step>maxd){
maxd=step;
maxi=x;
}
for(int i=head[x]; i!=-; i=e[i].next)
if(e[i].v!=prex) dfs(e[i].v,x,step+);
} void check(int a[],int n){
for(int i=;i<n;i++)
printf("%d ",a[i]);
puts("");
} int main()
{
int i,x,y,z;
while(scanf("%d%d%d",&n,&m,&q)!=EOF){
memset(head,-,sizeof(head));
en=;
REP(i,m) {
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
for(i=; i<=n ;i++)
f[i]=i;
for(i=; i<=n; i++)
if(f[i]==i){
maxd=-;
thefather=i;
dfs(i,-,);
maxd=-;
thefather=maxi;
dfs(thefather,-,);
md[thefather]=maxd;
}
REP(i,q){
scanf("%d",&z);
if(z==){
scanf("%d",&x);
printf("%d\n",md[getfather(x)]);
}else{
scanf("%d%d",&x,&y);
link(x,y);
// check(md,n+1);
// check(f,n+1);
}
}
}
return ;
}