[题解] NOI2018 归程（Kruskal重构树）

Contents

1 题目描述
2 输入格式
3 输出格式
4 样例输入1
5 样例输出1
6 样例输入2
7 样例输出2
8 数据范围
9 Kruskal 重构树
10 解题思路
11 代码

题目描述

本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。魔力之都可以抽象成一个 $n$ 个节点、$m$ 条边的无向连通图（节点的编号从 $1$ 至 $n$）。我们依次用 $l, a$ 描述一条边的长度、海拔。作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。

Yazid 是一名来自魔力之都的OIer，刚参加完ION2018 的他将踏上归程，回到他温暖的家。 Yazid 的家恰好在魔力之都的 $1$ 号节点。对于接下来 $Q$ 天，每一天 Yazid 都会告诉你他的出发点 $v$ ，以及当天的水位线 $p$。每一天，Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。 Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。需要特殊说明的是，第二天车会被重置，这意味着：

车会在新的出发点被准备好。
Yazid 不能利用之前在某处停放的车。
Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。本题的部分测试点将强制在线，具体细节请见【输入格式】和【子任务】。

输入格式

单个测试点中包含多组数据。输入的第一行为一个非负整数 $T$，表示数据的组数。

接下来依次描述每组数据，对于每组数据：

第一行 $2$ 个非负整数 $n$, $m$，分别表示节点数、边数。

接下来 $m$ 行，每行 $4$ 个正整数 $u, v, l, a$，描述一条连接节点 $u, v$ 的、长度为 $l$、海拔为 $a$ 的边。在这里，我们保证$1 \leq u,v \leq n$。

接下来一行 $3$ 个非负数 $Q, K, S$ ，其中 $Q$ 表示总天数，$K \in {0,1}$ 是一个会在下面被用到的系数，$S$ 表示的是可能的最高水位线。

接下来 $Q$ 行依次描述每天的状况。每行 $2$ 个整数 $v_0, p_0$ 描述一天：
这一天的出发节点为 $v = (v_0 + K \times \mathrm{lastans} – 1) \bmod n + 1$
这一天的水位线为 $p = (p_0 + K \times \mathrm{lastans}) \bmod (S + 1)$

其中 lastans 表示上一天的答案（最小步行总路程）。特别地，我们规定第 $1$ 天时 lastans = 0。在这里，我们保证 $1 \leq v_0 \leq n,0 \leq p_0 \leq S$

对于输入中的每一行，如果该行包含多个数，则用单个空格将它们隔开。

输出格式

依次输出各组数据的答案。对于每组数据：
输出 $Q$ 行每行一个整数，依次表示每天的最小步行总路程。

样例输入1

样例输出1

样例输入2

样例输出2

数据范围

所有测试点均保证 $T\leq 3$，所有测试点中的所有数据均满足如下限制：

$n \leq 2 \times 10^5, m \leq 4 \times 10^5, Q \leq 4 \times 10^5, k \in {0, 1}, 1 \leq S \leq 10^9$
对于所有边 $l \leq 10^4, a \leq 10^9$
任意两点之间都直接或间接通过边相邻

Kruskal 重构树

Kruskal 重构树是一种基于 Kruskal 算法，在求解最小生成树的同时建出的一棵新树，具体的构造方法如下：

在 Kruskal 算法中，排序后对于一条从 $u$ 到 $v$ 的边，若 $u$ 和 $v$ 之间还没有被合并，那么新建一个节点 $t$，将 $u$ 的祖先和 $v$ 的祖先与 $t$ 相连。

查找祖先的过程可以由不带按秩合并的并查集解决。

它具有以下性质:

是一个二叉堆
原树两点之间边权的最大值是 Kruskal 重构树上 LCA 的权值
原树的所有节点在 Kruskal 重构树上都是叶子节点

cnt = n;
for(register int i=1; i<=m; i++){
    int a = US::find(edge[i].from);
    int b = US::find(edge[i].to);

    if(a != b){
        ++num;
        ++cnt;

        US::merge(a, cnt);
        US::merge(b, cnt);

        Tree::add(a, cnt);
        Tree::add(b, cnt);
    }

    if(num == n - 1)
        break;
}

解题思路

因为车只能在没有积水的路上行驶，车不能重复使用，所以每一天 Yazid 回家的过程都是一部分路开车，一部分路走路（开车或走路的距离都可能为 $0$）

问题就是找到一条可以开车从 $v$ 到达 $u$ 的路径，并且 $u$ 到 $1$ 的距离最短

任何一个节点到 $1$ 的距离可以由 Dijkistra 进行预处理

根据 Kruskal 重构树的性质，是一个二叉堆，所以我们可以按海拔降序排序，建一棵重构树，那么如果一个子树的根节点对应海拔大于积水深度，所有子树内叶子节点对应的原始节点均可互相到达

我们从 $v$ 开始向上倍增，找到一个海拔大于积水深度，且深度最小的节点即可，子树内所有叶子对应原始节点均可从 $v$ 到达。

通过 dfs 还可预处理一个子树内原始节点到 $1$ 的最小距离。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;
const int MAXN = 400000 + 10;
const int MAXM = 800000 + 10;
const int SIZ = 20;

inline int read(){
    int x = 0;
    char ch = getchar();

    while(ch < '0' || ch > '9')
        ch = getchar();

    while('0' <= ch && ch <= '9'){
        x = x*10 + ch - '0';
        ch = getchar();
    }

    return x;
}

namespace US{
    int fa[MAXN];

    inline void init(int n){
        for(register int i=1; i<=n; i++){
            fa[i] = i;
        }
    }

    inline int find(int x){
        int root = x;;

        while(root != fa[root])
            root = fa[root];

        while(x != root){
            int tmp = fa[x];
            fa[x] = root;
            x = tmp;
        }

        return root;
    }

    inline void merge(int a, int b){
        int fa_a = find(a);
        int fa_b = find(b);

        fa[fa_a] = fa_b;
    }
}

struct Edge{
    int from, to, high;
};

Edge edge[MAXN];

namespace Graph{
    int Head[MAXN], to[MAXM], Next[MAXM], w[MAXM];
    int tot = 1;

    long long dis[MAXN];

    inline void init(){
        tot = 1;

        memset(Head, 0, sizeof(Head));
        memset(Next, 0, sizeof(Next));
        memset(dis, 0x3f, sizeof(dis));
    } 

    inline void __add(int a, int b, int c){
        to[tot] = b;
        w[tot] = c;
        Next[tot] = Head[a];
        Head[a] = tot++;
    }

    inline void add(int a, int b, int c){
        __add(a, b, c);
        __add(b, a, c);
    }

    #define P pair<long long, int>

    inline void dij(){
        priority_queue<P, vector<P>, greater<P> >que;

        que.push(make_pair(0, 1));
        dis[1] = 0;

        while(!que.empty()){
            P front = que.top();
            que.pop();

            int id = front.second;

            if(front.first > dis[id]){
                continue;
            }

            for(register int i=Head[id]; i; i=Next[i]){
                int v = to[i];

                if(dis[v] > dis[id] + w[i]){
                    dis[v] = dis[id] + w[i];
                    que.push(make_pair(dis[v], v));
                }
            }
        }
    }

    #undef P
}

namespace Tree{
    int Head[MAXN], to[MAXM], Next[MAXM];
    int fa[MAXN][SIZ];

    long long val[MAXN];

    int tot = 1;

    inline void init(){
        tot = 1;

        memset(fa, 0, sizeof(fa));
        memset(Head, 0, sizeof(Head));
        memset(Next, 0, sizeof(Next));
        memset(val, 0x3f, sizeof(val));
    } 

    inline void __add(int a, int b){
        to[tot] = b;
        Next[tot] = Head[a];
        Head[a] = tot++;
    }

    inline void add(int a, int b){
        __add(a, b);
        __add(b, a);
    }   

    inline void dfs(int x, int f){
        val[x] = min(val[x], Graph::dis[x]);
        fa[x][0] = f;

        for(register int i=Head[x]; i; i=Next[i]){
            int v = to[i];

            if(v != f){
                dfs(v, x);

                val[x] = min(val[x], val[v]);
            }
        }
    }

    inline void calc(int n){
        for(register int i=1; i<=19; i++){
            for(register int j=1; j<=n; j++){
                fa[j][i] = fa[fa[j][i-1]][i-1];
            }
        }
    }
}

inline bool cmp(Edge a, Edge b){
    return a.high > b.high;
}

using Tree::val;
using Tree::fa;

int T, n, m;
int q, k, s;

int height[MAXN];

int cnt, num;
long long lastans;

int main(){
    T = read();

    while(T--){
        n = read();
        m = read();

        US::init(n << 1);
        Graph::init();
        Tree::init();

        memset(height, 0, sizeof(height));

        lastans = 0;

        for(register int i=1; i<=m; i++){
            int a = read();
            int b = read();
            int c = read();
            int d = read();

            Graph::add(a, b, c);

            edge[i].from = a;
            edge[i].to = b;
            edge[i].high = d;
        }

        cnt = n;
        num = 0;

        Graph::dij();

        sort(edge+1, edge+m+1, cmp);

        for(register int i=1; i<=m; i++){
            int a = US::find(edge[i].from);
            int b = US::find(edge[i].to);

            if(a != b){
                ++num;
                ++cnt;

                US::merge(a, cnt);
                US::merge(b, cnt);

                Tree::add(a, cnt);
                Tree::add(b, cnt);

                height[cnt] = edge[i].high;
            }

            if(num == n - 1)
                break;
        }

        Tree::dfs(cnt, 0);
        Tree::calc(cnt);

        q = read();
        k = read();
        s = read();

        while(q--){
            int v = read();
            int p = read();

            v = (v + k * lastans - 1) % n + 1;
            p = (p + k * lastans) % (s + 1);

            for(register int i=19; i>=0; i--){
                if(height[fa[v][i]] > p){
                    v = fa[v][i];
                }
            }

            printf("%lld\n", lastans = val[v]);
        }

    }

    return 0;
}