Prelude
快要THUWC了，练一练板子。
传送到LOJ：o(TヘTo)
Solution
首先有一条定理。
到树中任意一点的最远点一定是直径的两个端点之一。
我也不会证反正大家都在用，似乎可以用反证法搞一搞？
然后就是LCT和并查集随便做了。
对于每个连通块，只需要保存这个连通块的直径的两个端点就可以了。
然后合并两个连通块的时候更新一下。
Code
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cctype>
using namespace std;
const int N = 300010;
int _w;
int read() {
int x = 0, ch;
while( isspace(ch = getchar()) );
do x = x * 10 + ch - '0';
while( isdigit(ch = getchar()) );
return x;
}
int type, n, q, lastans;
namespace LCT {
struct Node {
int sz;
Node *ch[2], *pa, *pathpa;
bool rev;
Node() {
ch[0] = ch[1] = pa = pathpa = NULL;
sz = 1, rev = 0;
}
int relation() {
return this == pa->ch[0] ? 0 : 1;
}
Node *pushdown() {
if( rev ) {
rev = 0;
swap( ch[0], ch[1] );
if( ch[0] ) ch[0]->rev ^= 1;
if( ch[1] ) ch[1]->rev ^= 1;
}
return this;
}
Node *maintain() {
sz = 1;
if( ch[0] ) sz += ch[0]->sz;
if( ch[1] ) sz += ch[1]->sz;
return this;
}
Node *rotate() {
if( pa->pa ) pa->pa->pushdown();
pa->pushdown(), pushdown();
Node *old = pa;
int x = relation();
if( pa->pa ) pa->pa->ch[old->relation()] = this;
pa = pa->pa;
old->ch[x] = ch[x^1];
if( ch[x^1] ) ch[x^1]->pa = old;
ch[x^1] = old, old->pa = this;
swap(old->pathpa, pathpa);
return old->maintain(), maintain();
}
Node *splay() {
while( pa ) {
if( !pa->pa ) rotate();
else {
pa->pa->pushdown(), pa->pushdown();
if( relation() == pa->relation() )
pa->rotate(), rotate();
else rotate(), rotate();
}
}
return this;
}
Node *expose() {
Node *rc = splay()->pushdown()->ch[1];
if( rc ) {
ch[1] = rc->pa = NULL;
rc->pathpa = this;
maintain();
}
return this;
}
bool splice() {
if( !splay()->pathpa ) return false;
pathpa->expose()->ch[1] = this;
pa = pathpa, pathpa = NULL;
pa->maintain();
return true;
}
Node *access() {
expose();
while( splice() );
return this;
}
Node *evert() {
access()->rev ^= 1;
return this;
}
};
Node *rt[N];
void init() {
for( int i = 1; i <= n; ++i )
rt[i] = new Node;
}
void link( int u, int v ) {
rt[u]->evert()->pathpa = rt[v];
}
int query( int u, int v ) {
rt[u]->evert();
return rt[v]->access()->sz - 1;
}
}
namespace DSU {
int pa[N], du[N], dv[N];
void init() {
for( int i = 1; i <= n; ++i )
pa[i] = du[i] = dv[i] = i;
}
int find( int u ) {
return pa[u] == u ? u : pa[u] = find( pa[u] );
}
int uni( int u, int v ) {
u = find(u), v = find(v);
return pa[u] = v;
}
}
namespace Solve {
void init() {
DSU::init();
LCT::init();
}
void link( int u, int v ) {
using DSU::du;
using DSU::dv;
using DSU::find;
int u1 = du[find(u)], u2 = dv[find(u)];
int v1 = du[find(v)], v2 = dv[find(v)];
int w1 = LCT::query(u, u1) > LCT::query(u, u2) ? u1 : u2;
int w2 = LCT::query(v, v1) > LCT::query(v, v2) ? v1 : v2;
LCT::link(u, v);
int rt = DSU::uni(u, v);
int lenu = LCT::query(u1, u2);
int lenv = LCT::query(v1, v2);
int lenw = LCT::query(w1, w2);
// printf( "w1 = %d, w2 = %d, lenw = %d\n", w1, w2, lenw );
if( lenu >= lenv && lenu >= lenw )
du[rt] = u1, dv[rt] = u2;
else if( lenv >= lenu && lenv >= lenw )
du[rt] = v1, dv[rt] = v2;
else
du[rt] = w1, dv[rt] = w2;
// printf( "du = %d, dv = %d\n", du[rt], dv[rt] );
}
int query( int u ) {
using DSU::du;
using DSU::dv;
using DSU::find;
int u1 = du[find(u)], u2 = dv[find(u)];
return max( LCT::query(u, u1), LCT::query(u, u2) );
}
}
int main() {
type = read(), n = read(), q = read();
Solve::init();
while( q-- ) {
if( read() == 1 ) {
int u = read(), v = read();
u ^= type * lastans;
v ^= type * lastans;
Solve::link(u, v);
} else {
int u = read();
u ^= type * lastans;
printf( "%d\n", lastans = Solve::query(u) );
}
}
return 0;
}