题目（BZOJ）（数据加强）
题目（洛谷）（某种意义上也算数据加强）
...我可以说这是LCT裸题吗？
只需要离线操作，倒着加边就行了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
#include <cctype>
#include <vector>
#include <climits>
#include <ext/pb_ds/assoc_container.hpp>
#define llmax LLONG_MAX
#define llmin LLONG_MIN
using namespace std;
using namespace __gnu_pbds;
template <class _E> inline void read(_E &e){
e=0;bool ck=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
if(ck)e=-e;
}
const int N=100050;
const int M=1500500;
int n,m,Q;
struct querys{
int x,y,opt,ans;
int id;
}q[N];
struct edge{
int x,y,w;
int id;
bool del;
}e[M];
inline bool cmp1(const edge &x,const edge &y){
if (x.x==y.x) return x.y<y.y;
else return x.x<y.x;
}
inline bool cmp2(const edge &x,const edge &y){
return x.w<y.w;
}
inline bool cmp3(const edge &x,const edge &y){
return x.id<y.id;
}
int f[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
inline int findno(int x,int y){
int l=1,r=m,mid;
while(l<=r){
mid=(l+r)>>1;
if (e[mid].x<x||(e[mid].x==x&&e[mid].y<y))l=mid+1;
else if (e[mid].x==x&&e[mid].y==y)return mid;
else r=mid-1;
}
return -1;
}
struct LCT{
int a[M],mx[M],fa[M],que[M],ch[M][2],top;bool rev[M];
inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
inline void pushup(int x){
int l=ch[x][0],r=ch[x][1];
mx[x]=x;
if(a[mx[l]]>a[mx[x]])mx[x]=mx[l];
if(a[mx[r]]>a[mx[x]])mx[x]=mx[r];
}
inline void pushdown(int x){
int l=ch[x][0],r=ch[x][1];
if(rev[x]){
rev[x]^=1;rev[l]^=1;rev[r]^=1;
swap(ch[x][0],ch[x][1]);
}
}
inline void roll(int x){
int y=fa[x],z=fa[y],l,r;
l=(ch[y][0]==x)^1;r=l^1;
if(!isroot(y)){if(ch[z][0]==y)ch[z][0]=x;else ch[z][1]=x;}
fa[x]=z;fa[y]=x;fa[ch[x][r]]=y;
ch[y][l]=ch[x][r];ch[x][r]=y;
pushup(y);pushup(x);
}
inline void splay(int x){
que[top=1]=x;
for(int i=x;!isroot(i);i=fa[i])que[++top]=fa[i];
for(int i=top;i;--i)pushdown(que[i]);
while(!isroot(x)){
int y=fa[x],z=fa[y];
if(!isroot(y)){if((ch[y][0]==x)^(ch[z][0]==x))roll(x);else roll(y);}roll(x);
}
}
inline void access(int x){for(int i=0;x;i=x,x=fa[x])splay(x),ch[x][1]=i,pushup(x);}
inline void makeroot(int x){access(x);splay(x);rev[x]^=1;}
inline int find(int x){access(x);splay(x);while(ch[x][0])x=ch[x][0];return x;}
inline void split(int x,int y){makeroot(x);access(y);splay(y);}
inline void cut(int x,int y){split(x,y);if(ch[y][0]==x)ch[y][0]=0,fa[x]=0;}
inline void link(int x,int y){makeroot(x);fa[x]=y;}
inline int query(int x,int y){split(x,y);return mx[y];}
}lct;
int main(){
read(n),read(m),read(Q);
for (int i=1;i<=m;++i){
int x,y,t;read(x),read(y),read(t);
if(x>y)swap(x,y);
e[i].x=x,e[i].y=y,e[i].w=t;
}
sort(e+1,e+m+1,cmp2);
for (int i=1;i<=m;++i){
e[i].id=i;
lct.mx[n+i]=n+i;
lct.a[n+i]=e[i].w;
}
sort(e+1,e+m+1,cmp1);
for (int i=1;i<=Q;++i){
read(q[i].opt),read(q[i].x),read(q[i].y);
if (q[i].opt==2){
if(q[i].x>q[i].y)swap(q[i].x,q[i].y);
int t=findno(q[i].x,q[i].y);
q[i].id=e[t].id;e[t].del=1;
}
}
sort(e+1,e+m+1,cmp3);
int cnt=0;
for (int i=1;i<=n;++i) f[i]=i;
for (int i=1;i<=m;++i){
if (e[i].del) continue;
int px=find(e[i].x),py=find(e[i].y);
if(f[px]!=py){
f[px]=py;
lct.link(e[i].x,i+n);
lct.link(e[i].y,i+n);
++cnt;
if(cnt==n-1)break;
}
}
for (int i=Q;i;--i){
if (q[i].opt==1){
q[i].ans=lct.a[lct.query(q[i].x,q[i].y)];
continue;
}
int x=q[i].x,y=q[i].y,k=q[i].id;
int tmp=lct.query(x,y);
if (e[k].w<lct.a[tmp]){
lct.cut(e[tmp-n].x,tmp);lct.cut(e[tmp-n].y,tmp);
lct.link(x,k+n);lct.link(y,k+n);
}
}
for (int i=1;i<=Q;++i){
if(q[i].opt==1)printf("%d\n",q[i].ans);
}
return 0;
}
Comments NOTHING