NOI模拟赛(3.13)Hike (远行)

Description

Mirada生活的城市中有N个小镇，一开始小镇之间没有任何道路连接。随着经济发展，小镇之间陆续建起了一些双向的道路，但是由于经济不太发达，在建设过程中，会保证对于任意两个小镇，最多有一条路径能互相到达。有的时候Miranda会从某个小镇开始进行徒步旅行，每次出发前，她都想选择一个她能到达的最远的小镇作为终点，并且她在行走过程中是不会走回头路的，为了估算这次旅行的时间，她会需要你告诉她这次旅行需要的时间会是多少呢？可以假设通过每条道路都需要单位时间，并且Miranda不会在小镇停留。

Input

第一行输入一个整数type，表示数据类型。
第二行两个整数N，Q。
接下来Q行，每行先读入一个整数ty，若ty=1，则接下来读入两个整数u，v，表示小镇u与小镇v建立了一条新道路。若ty=2，读入一个整数u，表示Miranda要开始一次从小镇u出发的旅行。
注意：
若type=1，表示数据进行了加密。记lstans表示最近一次Miranda旅行的时间，那么对于每次操作的u或u，v，都要异或上lstans，即u=u ^ lstans，v=v ^ lstans。
若type=0，则不需要对数据进行处理。

Output

对于每次询问，输出Miranda能到达的最远的小镇的距离是多少。注意Miranda可能只能留在开始的小镇。

Sample Input

Sample Output

Data Constraint

对于20%的数据，满足：N<=5000，Q<=10000
对于50%的数据，满足：N<=100000，Q<=200000
另外有20%的数据，满足：type=0
对于100%的数据，满足：N<=300000，Q<=500000，type=0或1，解密后的u,v满足1<=u,v<=N，且道路的修建会满足：每一个时刻，都不存在u,v，使得u,v之间能通过多种方式到达

Solution

操作有加边和维护联通块的最远端点，可以用LCT做

抄标程的，根本不会写啊

复杂度为O((N+Q) log N)

#include <stdio.h>

#include <string.h>

#define rg register

#define dmax(a, b) ((a) > (b) ? (a) : (b))

inline int rd()

	{

	rg int x = 0, c = getchar(), f = 1;

	for(; c < 48 || c > 57; c = getchar()) if(c == 45) f = -1;

	for(; c > 47 && c < 58; c = getchar()) x = (x << 1) + (x << 3) + c - 48;

	return x * f;

	}

inline void dswap(rg int &x, rg int &y)

	{

	x ^= y ^= x ^= y;

	}

const int N = 500010;

int on_line, n, Q, bel[N], dia[N][2];

struct node

	{

	bool rev;

	int sz, ch[2], fa;

	}T[N];

int find(rg int x) {return bel[x] == x ? x : bel[x] = find(bel[x]);}

inline void update(rg int u) {if(u) T[u].sz = T[T[u].ch[0]].sz + T[T[u].ch[1]].sz + 1;}

inline bool is_root(rg int u) {rg int fa = T[u].fa; return !fa || !(T[fa].ch[0] == u || T[fa].ch[1] == u);}

inline void setch(rg int u, rg int v, rg int c)

	{

	T[u].ch[c] = v;

	if(v) T[v].fa = u;

	}

inline void mark(rg int u)

	{

	if(!u)return;

	T[u].rev ^= 1;

	dswap(T[u].ch[0], T[u].ch[1]);

	}

inline void down(rg int u)

	{

	if(!T[u].rev)return;

	mark(T[u].ch[0]);

	mark(T[u].ch[1]);

	T[u].rev = 0;

	}

inline void rotate(rg int u)

	{

	int fa = T[u].fa, ft = T[fa].fa, c = T[fa].ch[1] == u;

	T[u].fa = ft;

	if(!is_root(fa)) setch(ft, u, T[ft].ch[1] == fa);

	setch(fa, T[u].ch[!c], c);

	setch(u, fa, !c);

	update(fa);

	}

inline void splay(rg int u)

	{

	static int stack[N];

	rg int top = 0, p = u;

	for(; !is_root(p); p = T[p].fa) stack[++top] = p;

	stack[++top] = p;

	for(; top; top--) down(stack[top]);

	for(; !is_root(u); rotate(u))

		{

		rg int fa = T[u].fa, ft = T[fa].fa;

		if(is_root(fa)) continue;

		((T[ft].ch[1] == fa) ^ (T[fa].ch[1] == u)) ? rotate(u) : rotate(fa);

		}

	update(u);

	}

inline int access(rg int u)

	{

	int nxt = 0;

	for(; u; nxt = u, u = T[u].fa) splay(u), T[u].ch[1] = nxt, update(u);

	return nxt;

	}

inline void make_root(rg int u) {mark(access(u));}

inline void link(rg int u, rg int v)

	{

	make_root(v);

	splay(v);

	T[v].fa = u;

	access(v);

	}

inline int get_dis(rg int u, rg int v)

	{

	make_root(u);

	access(v);

	splay(v);

	return T[v].sz - 1;

	}

inline void merge(rg int a, rg int b)

	{

	rg int u = find(a), v = find(b);

	bel[v] = u;

	link(a, b);

	rg int lu = dia[u][0], lv = dia[u][1], h = get_dis(dia[u][0], dia[u][1]);

	rg int h1 = get_dis(dia[v][0], dia[v][1]);

	if(h1 > h) lu = dia[v][0], lv = dia[v][1], h = h1;

	for(rg int i = 0; i < 2; i++)

		for(rg int j = 0; j < 2; j++)

			{

			h1 = get_dis(dia[u][i], dia[v][j]);

			if(h1 > h) lu = dia[u][i], lv = dia[v][j], h = h1;

			}

	dia[u][0] = lu, dia[u][1] = lv;

	}

int main()

	{

	freopen("hike.in", "r", stdin), freopen("hike.out", "w", stdout);

	on_line = rd(), n = rd(), Q = rd();

	for(rg int i = 1; i <= n; i++) bel[i] = dia[i][0] = dia[i][1] = i;

	rg int last_ans = 0;

	while(Q--)

		{

		rg int ty = rd();

		if(ty & 1)

			{

			rg int u = rd(), v = rd();

			if(on_line) u ^= last_ans, v ^= last_ans;

			merge(u, v);

			}

		else{

			rg int u = rd();

			if(on_line) u ^= last_ans;

			rg int p = find(u);

			printf("%d\n", last_ans = dmax(get_dis(u, dia[p][0]), get_dis(u, dia[p][1])));

			}

		}

	fclose(stdin), fclose(stdout);

	return 0;

	}

巴特西