考虑先分析一下题目给的性质啊：
道路的修建会满足：每一时刻，都不存在 ((u,v)) 使得 ((u,v)) 之间能通过多种方式到达。
妥妥的一棵树啊。
通过每条道路都需要单位时间
这棵树的边权为(1)
她都想选择一个她能到达的最远的小镇作为终点，并且她在行走过程中是不会走回头路的
就是找一个最远点，让(dis(u,k))最长，在树上的话，我们知道这个点(k)是这颗树上直径的两端之一。
所以我们需要记录直径端点
小镇之间陆续建起了一些双向的道路
两颗子树连在一起了，我们要维护出合并之后的树的直径端点，有一个性质就是：这个两个端点一定是原两棵树的直径四个端点之二。
那么我们只要六种情况都试一下就好了。
那么我们需要做什么：
动态维护树上路径。
维护每一颗树的直径端点。
那么(LCT),(DSU)。
「雅礼集训 2017 Day5」珠宝
#include<iostream>
#include<cstdio>
#define ll long long
#define N 3000005
//___________________
ll f[N],c[N][2],siz[N],st[N];
bool ri[N];
#define l(x) c[x][0]
#define r(x) c[x][1]
inline bool nroot(int x){return l(f[x]) == x || r(f[x]) == x;}
inline void up(int x){siz[x] = (siz[l(x)] + siz[r(x)] + 1);}
inline void pushr(int x){std::swap(l(x),r(x));ri[x] ^= 1;}
inline void pushdown(int x){
if(ri[x]){
if(l(x))pushr(l(x));
if(r(x))pushr(r(x));
ri[x] = 0;
}
}
inline void rotate(int x){
int y = f[x],z = f[y],k = r(y) == x,w = c[x][!k];
if(nroot(y))
c[z][r(z) == y] = x;c[x][!k] = y;c[y][k] = w;
if(w)
f[w] = y;f[y] = x;f[x] = z;
up(y);up(x);
}
inline void splay(int x){
ll y = x,z = 0;
st[++z] = y;
while(nroot(y))st[++z] = y = f[y];
while(z)pushdown(st[z -- ]);
while(nroot(x)){
ll y = f[x],z = f[y];
if(nroot(y))
rotate((l(y) == x) ^ (l(z) == y) ? x : y);
rotate(x);
}
up(x);
}
inline void access(int x){
for(int y = 0;x;x = f[y = x])
splay(x),r(x) = y,up(x);
}
inline void makeroot(int x){access(x),splay(x),pushr(x);}
inline void split(int x,int y){makeroot(x),access(y),splay(y);}
inline void link(int x,int y){makeroot(x);f[x] = y;}
//__________________LCT
ll fa[N],l[N],r[N];
inline ll find(int x){return (fa[x] == x) ? x : fa[x] = find(fa[x]);}
inline void merge(int x,int y){//x -> y
ll ans = 0,ansl,ansr;
fa[x] = y;
split(l[x],r[x]);
if(siz[r[x]] - 1 > ans)
ans = siz[r[x]] - 1,ansl = l[x],ansr = r[x];
split(l[y],r[x]);
if(siz[r[x]] - 1 > ans)
ans = siz[r[x]] - 1,ansl = l[y],ansr = r[x];
split(l[x],r[y]);
if(siz[r[y]] - 1 > ans)
ans = siz[r[y]] - 1,ansl = l[x],ansr = r[y];
split(l[y],r[y]);
if(siz[r[y]] - 1 > ans)
ans = siz[r[y]] - 1,ansl = l[y],ansr = r[y];
split(l[x],l[y]);
if(siz[l[y]] - 1 > ans)
ans = siz[l[y]] - 1,ansl = l[x],ansr = l[y];
split(r[x],r[y]);
if(siz[r[y]] - 1 > ans)
ans = siz[r[y]] - 1,ansl = r[x],ansr = r[y];
l[y] = ansl,r[y] = ansr;
// std::cout<<x<<" "<<y<<" "<<l[y]<<" "<<r[y]<<std::endl;
}
//__________________DSU
ll n,q,type,last;
int main(){
scanf("%lld",&type);
scanf("%lld%lld",&n,&q);
for(int i = 1;i <= n;++i)
fa[i] = l[i] = r[i] = i;
while(q -- ){
ll opt,u,v;
scanf("%lld",&opt);
if(opt == 1){
scanf("%lld%lld",&u,&v);
u ^= type * last;
v ^= type * last;
link(u,v);
merge(find(u),find(v));
}else{
scanf("%lld",&u);
u ^= type * last;
ll al = l[find(u)],ar = r[find(u)];
ll ans = 0;
// std::cout<<al<<" "<<ar<<std::endl;
split(al,u);
ans = std::max(ans,siz[u] - 1);
split(ar,u);
ans = std::max(ans,siz[u] - 1);
std::cout<<(last = ans)<<std::endl;
}
}
}