由于懒癌，好久以前就从洛咕日报上有这么个科技了，但是现在才学。

有一种题目就是限制我们边权只能走<=x或>=x的，这种题目显然我们可以离线+kruskal维护，但是他强制在线就有点蛋疼了，这时我们可以用一棵二叉树记录kruskal的合并顺序，在树上搞搞倍增什么的做到在线处理。

具体地说，我们在kruskal合并连通块时，新建一个节点，将当前枚举边的边权赋予这个节点，让这个节点成为这两个连通块代表节点的父亲，并让这个节点成为新连通块的代表节点。

显然，我们最后形成了一棵满足二叉堆性质的树。我们在树上瞎搞搞就可以在线处理。

例如，我们要查询无向图中从某个点p开始经过<=x的边能到达点的数量。我们建立大根Kruskal重构树，维护倍增信息，我们在树上倍增跳p的父亲，直到跳到<=x的最大的点为止，这个子树中叶子节点的数量即为答案。

例题：[NOI2018]归程

做了这题后发现非常水。题目大意就是每次询问从一个节点v开始走，经过边的海拔>p能走到所有点中，距离1号点的距离中最短的是什么。我们先从1号节点跑一遍dij求出所有最短路，然后建立小根Kruskal重构树，对于每个点维护子树中到1号点距离最短的点的距离。在Kruskal树上倍增条到海拔>p的深度最小的那个点，输出那个点存储的最短距离即可。

代码写的不算太丑，就放上来吧。（其实也挺丑的）

#include 
    
     using namespace std;struct edge{    int v, w, ne;} a[4000010];struct fuck{    int u, v, a;} e[2000010];int h[2000010], tmp;int dis[4000010], ds[4000010], fa[4000010][23], val[4000010];bool v[2000010];int n, m;void add(int x, int y, int z){    a[++tmp] = (edge){y, z, h[x]};    h[x] = tmp;}bool operator>(const fuck &x, const fuck &y){    return x.a > y.a;}int getf(int x){    return ds[x] == x ? x : ds[x] = getf(ds[x]);}void work(){    scanf("%d%d", &n, &m);    tmp = 0;    for (int i = 1; i <= n; i++)        h[i] = 0, dis[i] = val[i] = 0x3f3f3f3f, v[i] = false, ds[i] = i, fa[i][0] = 0;    for (int t, i = 1; i <= m; i++)    {        scanf("%d%d%d%d", &e[i].u, &e[i].v, &t, &e[i].a);        add(e[i].u, e[i].v, t), add(e[i].v, e[i].u, t);    }    priority_queue
     
      
       , vector
       
        
          >, greater
         
          
            > > que; que.push(make_pair(0, 1)); dis[1] = 0; while (!que.empty()) { int x = que.top().second; que.pop(); if (v[x] == true) continue; v[x] = true; for (int i = h[x]; i != 0; i = a[i].ne) if (v[a[i].v] == false && dis[x] + a[i].w < dis[a[i].v]) dis[a[i].v] = dis[x] + a[i].w, que.push(make_pair(dis[a[i].v], a[i].v)); } sort(e + 1, e + 1 + m, greater
           
            ()); int tot = n; for (int i = 1; i <= m; i++) { int f1 = getf(e[i].u), f2 = getf(e[i].v); if (f1 != f2) { int p = ++tot; ds[p] = p; fa[p][0] = 0; val[p] = e[i].a; dis[p] = min(dis[f1], dis[f2]); ds[f1] = p; ds[f2] = p; fa[f1][0] = p; fa[f2][0] = p; } } for (int j = 1; j <= 19; j++) for (int i = 1; i <= tot; i++) fa[i][j] = fa[fa[i][j - 1]][j - 1]; int q, k, s, lastans = 0; val[0] = -2333; scanf("%d%d%d", &q, &k, &s); for (int v, p, i = 1; i <= q; i++) { scanf("%d%d", &v, &p); v = (v + k * lastans - 1) % n + 1; p = (p + k * lastans) % (s + 1); for (int i = 19; i >= 0; i--) if (val[fa[v][i]] > p) v = fa[v][i]; printf("%d\n", lastans = dis[v]); }}int main(){ int t; scanf("%d", &t); while (t --> 0) { work(); } return 0;}
           
          
         
        
       
      
     
    

还有一道题是BZOJ3545 Peaks，要用Kruskal重构树+主席树合并维护

代码还没写呢，该好好复习一遍主席树去了。