NKOJ 2698 Nicole's blog (Dynamic Trees + Minimum Spanning Trees)

P2698【动态树】Nicole的博客

问题描述

给定一个包含N个顶点和M条加权边的无向简单图G=(V,E)，执行以下Q次操作：
·1号操作：询问连接顶点x和y的一条路径P，并使路径P上的最大权重最小化；
·2号操作：删除当前存在的连接顶点x和y的一条特定边e；
对于每一次1号操作请求的结果，请输出该路径P上具有最大权重的那个边所对应的权重值。

输入格式

首先给出三个整数值N、M、Q。
之后，在接下来的M行中每一行为三个整数值x、y及z。
每一行具体表示：节点x与节点y之间存在一条边其权重为z。
同时，在后续Q次操作中：
每一次查询或更新操作均涉及参数k以及两个节点x和y。

输出格式

对每次询问输出一行

样例输入

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

提示

1<=N<=100000
1<=M<=1000000
1<=Q<=100000
1<=x,y<=N
1<=z<=109
保证任意时刻整个图连通