kruskal重构树

---

Description

给你N个点的无向图 (1 <= N <= 15,000)，记为：1…N。

图中有M条边 (1 <= M <= 30,000) ，第j条边的长度为： d_j ( 1 < = d_j < = 1,000,000,000).

现在有 K个询问 (1 < = K < = 15,000)。

每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少？

Input

第一行： N, M, K。

第2..M+1行: 三个正整数：X, Y, and D (1 <= X <=N; 1 <= Y <= N). 表示X与Y之间有一条长度为D的边。

第M+2..M+K+1行: 每行两个整数A B,表示询问从A点走到B点的所有路径中，最长的边最小值是多少？

Output

对每个询问，输出最长的边最小值是多少。

Sample Input

6 6 8

1 2 5

2 3 4

3 4 3

1 4 8

2 5 7

4 6 2

1 2

1 3

1 4

2 3

2 4

5 1

6 2

6 1

Sample Output

5

5

5

4

4

7

4

5

Hint

1 <= N <= 15,000

1 <= M <= 30,000

1 <= d_j <= 1,000,000,000

1 <= K <= 15,000

---

Solution

首先如果这道题是可以离线的，那么我们可以将边从小到大排序，每次加边，然后把两个端点所在的联通块并在一起。那么当A，B刚好联通时加的那条边的边权就是答案。但是本题强制在线，所以我们必须先预处理再回答询问。

我们按照kruskal求最小生成树的方式加边，但每次在加边时，新建一个节点，然后把两个联通块（其实是两棵二叉树）的根节点作为其左右儿子，把边权赋值给新建节点。那么我们可以发现这棵树有几个性质。

1. 是一棵二叉树（虽然这道题并没有什么卵用）；
2. 满足父节点的值大于等于儿子节点，是一个大顶堆，这是最关键的一点；
3. 原图上任意两点间路径最长边的最小值等于其lca的值；

这种建树的方法称作kruskal重构树。

那么A，B的lca就是所求答案。

Code

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn = 3e4 + 5; int n, m, q, cnt, x, y;int fa[maxn << 1], f[maxn << 1][20], dep[maxn << 1], val[maxn << 1], ch[maxn << 1][2];int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}struct edge {    int u, v, w;    bool operator < (const edge &a) const {return w < a.w;}} e[maxn << 1];inline int ask(int u, int v) {    if(dep[u] < dep[v]) swap(u, v);    int t = dep[u] - dep[v];    for(int i = 0; i < 20; i++) if(t & (1<