[WC2006]水管局长

X.[WC2006]水管局长

或许我这题应该放到V.[NOI2014]魔法森林前面的QaQ？

这题首先一眼看出翻转加边顺序。然后，动态维护最小生成森林，这样保证最小生成森林上的路径上的最大值就是原图中路径的最大值的可能的最小值。反正随便写写就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define lson t[x].ch[0]
#define rson t[x].ch[1]
int n,m,q;
struct LCT{
	int ch[2],fa,val,mx,rev;
}t[1001000];
int identify(int x){
	if(t[t[x].fa].ch[0]==x)return 0;
	if(t[t[x].fa].ch[1]==x)return 1;
	return -1;
}
void pushup(int x){
	t[x].mx=x;
	if(lson&&t[t[lson].mx].val>t[t[x].mx].val)t[x].mx=t[lson].mx;
	if(rson&&t[t[rson].mx].val>t[t[x].mx].val)t[x].mx=t[rson].mx;
}
void REV(int x){
	t[x].rev^=1,swap(lson,rson);
}
void pushdown(int x){
	if(!t[x].rev)return;
	if(lson)REV(lson);
	if(rson)REV(rson);
	t[x].rev=false;
}
void rotate(int x){
	int y=t[x].fa;
	int z=t[y].fa;
	int dirx=identify(x);
	int diry=identify(y);
	int b=t[x].ch[!dirx];
	if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
	if(b)t[b].fa=y;t[y].ch[dirx]=b;
	t[y].fa=x,t[x].ch[!dirx]=y;
	pushup(y),pushup(x);
}
void pushall(int x){
	if(identify(x)!=-1)pushall(t[x].fa);
	pushdown(x);
}
void splay(int x){
	pushall(x);
	while(identify(x)!=-1){
		int fa=t[x].fa;
		if(identify(fa)==-1)rotate(x);
		else if(identify(fa)==identify(x))rotate(fa),rotate(x);
		else rotate(x),rotate(x);
	}
}
void access(int x){
	for(int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
}
void makeroot(int x){
	access(x),splay(x),REV(x);
}
int findroot(int x){
	access(x),splay(x);
	pushdown(x);
	while(lson)x=lson,pushdown(x);
	splay(x);
	return x;
}
void split(int x,int y){
	makeroot(x),access(y),splay(y);
}
void link(int x,int y){
	makeroot(x),t[x].fa=y;
}
void cut(int x,int y){
	split(x,y),t[x].fa=t[y].ch[0]=0,pushup(y);
}
pair<int,int>p[100100];
struct query{
	int tp,x,y;
}r[100100];
bool des[100100];
map<pair<int,int>,int>mp;
void LINK(int id){
	if(findroot(p[id].first)!=findroot(p[id].second))link(p[id].first,id+n),link(p[id].second,id+n);
	else{
		split(p[id].first,p[id].second);
		int tmp=t[p[id].second].mx;
		if(t[tmp].val<=t[id+n].val)return;
		cut(tmp,p[tmp-n].first),cut(tmp,p[tmp-n].second);
		link(p[id].first,id+n),link(p[id].second,id+n);
	}
}
stack<int>S;
int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&p[i].first,&p[i].second,&t[i+n].val);
		if(p[i].first>p[i].second)swap(p[i].first,p[i].second);
		mp[p[i]]=i;
	}
	for(int i=1;i<=q;i++){
		scanf("%d%d%d",&r[i].tp,&r[i].x,&r[i].y);
		if(r[i].x>r[i].y)swap(r[i].x,r[i].y);
		if(r[i].tp==2)des[mp[make_pair(r[i].x,r[i].y)]]=true;
	}
	for(int i=1;i<=m;i++)if(!des[i])LINK(i);
	for(int i=q;i;i--)if(r[i].tp==2)LINK(mp[make_pair(r[i].x,r[i].y)]);else split(r[i].x,r[i].y),S.push(t[t[r[i].y].mx].val);
	while(!S.empty())printf("%d\n",S.top()),S.pop();
	return 0;
}