【Luogu】P4172水管局长(LCT)

时间:2022-12-29 09:40:49

  题目链接

  有个结论是x到y的路径上最长边权值等于最小生成树上最长边权值,于是问题转化为最小生成树。

  再考虑把问题反过来,删边变成加边。

  于是变成动态维护最小生成树,LCT可以做到。

  

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<map>
#define maxn 200020
using namespace std;
inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} struct Edge{
int from,to,val;
bool operator <(const Edge &a)const{ return val<a.val; }
}edge[maxn]; int stack[maxn],top; struct Splay{
struct Node{
int e[],fa,mini,tag,val,maxi;
}tree[maxn];
inline int iden(int x){ return x==tree[tree[x].fa].e[]; }
inline void connect(int x,int fa,int how){ tree[x].fa=fa; tree[fa].e[how]=x; }
inline bool isroot(int x){ return tree[tree[x].fa].e[]!=x&&tree[tree[x].fa].e[]!=x; }
inline void update(int x){
int le=tree[x].e[],ri=tree[x].e[]; tree[x].maxi=tree[x].val;
if(edge[tree[le].maxi].val>edge[tree[x].maxi].val) tree[x].maxi=tree[le].maxi;
if(edge[tree[ri].maxi].val>edge[tree[x].maxi].val) tree[x].maxi=tree[ri].maxi;
}
inline void reverse(int x){
swap(tree[x].e[],tree[x].e[]);
tree[x].tag^=;
}
inline void pushdown(int x){
if(tree[x].tag==) return;
if(tree[x].e[]) reverse(tree[x].e[]);
if(tree[x].e[]) reverse(tree[x].e[]);
tree[x].tag=;
}
void rotate(int x){
int y=tree[x].fa,r=tree[y].fa;
int sony=iden(x),sonr=iden(y);
tree[x].fa=r; if(!isroot(y)) tree[r].e[sonr]=x;
int b=tree[x].e[sony^];
connect(b,y,sony);
connect(y,x,sony^);
update(y);
}
inline void pushto(int x){
top=;
while(!isroot(x)){
stack[++top]=x;
x=tree[x].fa;
}
pushdown(x);
while(top) pushdown(stack[top--]);
}
void splay(int x){
pushto(x);
while(!isroot(x)){
int fa=tree[x].fa;
if(!isroot(fa))
if(iden(fa)==iden(x)) rotate(fa);
else rotate(x);
rotate(x);
}
update(x);
}
inline void access(int x){
int last=;
while(x){
splay(x);
tree[x].e[]=last;
update(x);
last=x; x=tree[x].fa;
}
}
inline void makeroot(int x){
access(x);
splay(x);
reverse(x);
}
inline int findroot(int x){
access(x);
splay(x);
while(tree[x].e[]) x=tree[x].e[];
return x;
}
inline void split(int x,int y){
makeroot(x);
access(y);
splay(y);
}
inline void link(int x,int y){
//printf("%d %d\n",x,y);
split(x,y);
tree[x].fa=y;
}
inline void cut(int x,int y){
//printf("%d %d\n",x,y);
split(x,y);
if(tree[y].e[]!=x||tree[x].e[]) return;
tree[x].fa=tree[y].e[]=;
}
}s; struct Que{
int opt,x,y,id,cnt;
}q[maxn];
int cnt; int ans[maxn]; int d[maxn*]; bool vis[maxn]; int main(){
int n=read(),m=read(),e=read();
for(int i=;i<=m;++i){
edge[i]=(Edge){read(),read(),read()};
if(edge[i].from>edge[i].to) swap(edge[i].from,edge[i].to);
}
sort(edge+,edge+m+);
for(int i=;i<=m;++i){
//printf("%d %d>><\n",edge[i].from,edge[i].to);
s.tree[i+n].mini=s.tree[i+n].val=i;
d[edge[i].from*n+edge[i].to]=i;
}
for(int i=;i<=e;++i){
q[i]=(Que){read(),read(),read(),};
if(q[i].x>q[i].y) swap(q[i].x,q[i].y);
if(q[i].opt==) q[i].id=++cnt;
else{
int now=d[q[i].x*n+q[i].y];
q[i].cnt=now;
//printf("%d\n",now);
vis[now]=;
}
}
int sum=;
for(int i=;i<=m;++i){
if(sum==n-) break;
if(vis[i]) continue;
if(s.findroot(edge[i].from)==s.findroot(edge[i].to)) continue;
s.link(edge[i].from,i+n);
s.link(edge[i].to,i+n);
sum++;
}
for(int i=e;i;--i){
if(q[i].opt==){
s.split(q[i].x,q[i].y);
ans[q[i].id]=edge[s.tree[q[i].y].maxi].val;
}
else{
s.split(q[i].x,q[i].y);
int now=q[i].cnt;
int ret=s.tree[q[i].y].maxi;
if(edge[now].val<edge[ret].val){
if(edge[ret].from) s.cut(edge[ret].from,ret+n);
if(edge[ret].to) s.cut(edge[ret].to,ret+n);
s.link(q[i].x,now+n);
s.link(q[i].y,now+n);
}
}
}
for(int i=;i<=cnt;++i) printf("%d\n",ans[i]);
return ;
}