题目

SC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。

在处理每项送水任务之前，路径上的水管都要进行一系列的准备操作，如清洗、消毒等等。嘟嘟在控制中心一声令下，这些水管的准备操作同时开始，但由于各条管道的长度、内径不同，进行准备操作需要的时间可能不同。供水公司总是希望嘟嘟能找到这样一条送水路径，路径上的所有管道全都准备就绪所需要的时间尽量短。嘟嘟希望你能帮助他完成这样的一个选择路径的系统，以满足供水公司的要求。另外，由于MY市的水管年代久远，一些水管会不时出现故障导致不能使用，你的程序必须考虑到这一点。

不妨将MY市的水管网络看作一幅简单无向图（即没有自环或重边）：水管是图中的边，水管的连接处为图中的结点。

输入格式

输入文件第一行为3个整数：N, M, Q分别表示管道连接处（结点）的数目、目前水管（无向边）的数目，以及你的程序需要处理的任务数目（包括寻找一条满足要求的路径和接受某条水管坏掉的事实）。

以下M行，每行3个整数x, y和t，描述一条对应的水管。x和y表示水管两端结点的编号，t表示准备送水所需要的时间。我们不妨为结点从1至N编号，这样所有的x和y都在范围[1, N]内。

以下Q行，每行描述一项任务。其中第一个整数为k：若k=1则后跟两个整数A和B，表示你需要为供水公司寻找一条满足要求的从A到B的水管路径；若k=2，则后跟两个整数x和y，表示直接连接x和y的水管宣布报废（保证合法，即在此之前直接连接x和y尚未报废的水管一定存在）。

输出格式

按顺序对应输入文件中每一项k=1的任务，你需要输出一个数字和一个回车/换行符。该数字表示：你寻找到的水管路径中所有管道全都完成准备工作所需要的时间（当然要求最短）。

输入样例

4 4 3

1 2 2

2 3 3

3 4 2

1 4 2

1 1 4

2 1 4

1 1 4

输出样例

2

3

提示

【原题数据范围】

N ≤ 1000

M ≤ 100000

Q ≤ 100000

测试数据中宣布报废的水管不超过5000条；且任何时候我们考虑的水管网络都是连通的，即从任一结点A必有至少一条水管路径通往任一结点B。

【加强版数据范围】

N ≤ 100000

M ≤ 1000000

Q ≤ 100000

任何时候我们考虑的水管网络都是连通的，即从任一结点A必有至少一条水管路径通往任一结点B。

题解

我们可以用LCT维护最小生成树，把每条边拆成一个有权值的点

每次询问直接查询两点间最大值

删边呢？

LCT维护最小生成树只支持加边操作

我们需要离线处理，反过来就相当于加边

加边时，询问两端点间的最大边，如果没有新边小，则断开这条边，两端点连上新边

【还是有很多细节的】

【这道题卡常】

【第一次求最小生成树用并查集会快很多】

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");

#define isrt(u) (!fa[u] || (ch[fa[u]][0] != u && ch[fa[u]][1] != u))

#define ls ch[u][0]

#define rs ch[u][1]

#define isr(u) (ch[fa[u]][1] == u)

using namespace std;

const int maxn = 100005,maxm = 1000005,maxv = 1100005,INF = 1000000000;

inline int RD(){

    int out = 0,flag = 1; char c = getchar();

    while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

    while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();}

    return out * flag;

}

int N,M,Q,ans[maxn];

struct EDGE{int u,v,w,id,ex;}ed[maxm];

inline bool operator <(const EDGE& a,const EDGE& b){

    return a.u == b.u ? a.v < b.v : a.u < b.u;

}

inline bool cmp(const EDGE& a,const EDGE& b){

    return a.w < b.w;

}

inline bool cmp2(const EDGE& a,const EDGE& b){

    return a.id < b.id;

}

struct Que{int u,v,k,id;}e[maxn];

int fa[maxv],mx[maxv],rev[maxv],ch[maxv][2],Val[maxv];

void upd(int u){

    mx[u] = u;

    if (Val[mx[ls]] > Val[mx[u]]) mx[u] = mx[ls];

    if (Val[mx[rs]] > Val[mx[u]]) mx[u] = mx[rs];

}

void pd(int u){

    if (rev[u]){

        swap(ls,rs); rev[ls] ^= 1; rev[rs] ^= 1; rev[u] ^= 1;

    }

}

void push_down(int u){

    if (!isrt(u)) push_down(fa[u]);

    pd(u);

}

void spin(int u){

    int s = isr(u),f = fa[u];

    fa[u] = fa[f]; if (!isrt(f)) ch[fa[f]][isr(f)] = u;

    ch[f][s] = ch[u][s ^ 1]; if (ch[u][s ^ 1]) fa[ch[u][s ^ 1]] = f;

    ch[u][s ^ 1] = f; fa[f] = u;

    upd(f); upd(u);

}

void splay(int u){

    for (push_down(u); !isrt(u); spin(u))

        if (!isrt(fa[u])) spin((isr(u) ^ isr(fa[u])) ? u : fa[u]);

}

void Access(int u){

    for (int v = 0; u; u = fa[v = u])

        splay(u),ch[u][1] = v,upd(u);

}

void Make_rt(int u){

    Access(u); splay(u); rev[u] ^= 1;

}

void Split(int u,int v){

    Make_rt(u); Access(v); splay(v);

}

void Link(int u,int v){

    Make_rt(u); fa[u] = v;

}

void Cut(int u,int v){

    Split(u,v); ch[v][0] = 0; fa[u] = 0; upd(v);

}

int Query(int u,int v){

    Split(u,v); return mx[v];

}

int finde(int u,int v){

    int L = 1,R = M,mid;

    while (L <= R){

        mid = L + R >> 1;

        if (ed[mid].u < u || (ed[mid].u == u && ed[mid].v < v)) L = mid + 1;

        else if (ed[mid].u == u && ed[mid].v == v) return mid;

        else R = mid - 1;

    }return L;

}

int pre[maxn];

int find(int u){return u == pre[u] ? u : pre[u] = find(pre[u]);}

int main(){

    N = RD(); M = RD(); Q = RD(); int u,v,a,b,k,x;

    REP(i,N + M) mx[i] = i;

    REP(i,M){

        a = RD(); b = RD(); x = RD();

        if (a > b) swap(a,b);

        ed[i] = (EDGE){a,b,x,i,true};

    }

    sort(ed + 1,ed + 1 + M,cmp);

    REP(i,M){

        ed[i].id = i;

        Val[N + i] = ed[i].w;

    }

    sort(ed + 1,ed + 1 + M);

    //REP(i,M) printf("[%d,%d] w = %d id = %d\n",ed[i].u,ed[i].v,ed[i].w,ed[i].id);

    REP(i,Q){

        k = RD(),a = RD(),b = RD(); x = 0;

        if (a > b) swap(a,b);

        if (k == 2){

            ed[x = finde(a,b)].ex = false;

            //printf("[%d,%d]  [%d,%d]\n",a,b,ed[x].u,ed[x].v);

        }

        e[i] = (Que){a,b,k,ed[x].id};

    }

    sort(ed + 1,ed + 1 + M,cmp2);

    int cnt = N,fu,fv,t;

    REP(i,N) pre[i] = i;

    for (int i = 1; i <= M && cnt > 1; i++){

        if (!ed[i].ex) continue;

        fu = find(u = ed[i].u); fv = find(v = ed[i].v); x = i + N;

        if (fu != fv){

            //printf("%d to %d  w = %d\n",u,v,ed[i].w);

            Link(u,x); Link(v,x);

            pre[fu] = fv; cnt--;

        }

    }

    for (int i = Q; i; i--){

        if (e[i].k & 1) ans[i] = Val[Query(e[i].u,e[i].v)];

        else {

            x = e[i].id;

            t = Query(u = e[i].u,v = e[i].v);

            if (ed[x].w < Val[t]){

                //printf("Cut %d-%d w = %d,Link %d to %d w = %d\n",ed[t - N].u,ed[t - N].v,Val[t],u,v,ed[x].w);

                Cut(ed[t - N].u,t),Cut(ed[t - N].v,t),Link(u,N + x),Link(v,N + x);

            }

        }

    }

    for (int i = 1; i <= Q; i++)

        if (e[i].k & 1) printf("%d\n",ans[i]);

    return 0;

}