归程

Posted on 2022-06-16 Edited on 2022-07-25 Views:

…

Solution

前置知识：$kruskal$重构树，这是个什么东西呢，我们都知道并查集为了保证时间复杂度需要按秩合并，这会导致一个什么样的结果呢？路径压缩了，那么如果我们使用$kruskal$算法跑最小生成树的话，我们所加入的边的信息就丢失了，一般来说我们是不需要这些信息的，但是某些时候这些信息就显得无比重要，更具体的$kruskal$重构树可以在某些情况下弥补这个问题，以下是它的建立：

按照$kruskal$的顺序将所有点连起来，但不是直接像按秩合并那样连起来，我们需要建立一个新节点，将这两个节点目前（除了这个节点未合并，不是它本身）的根连起来，然后这个点的点权就是加入边的边权。

这样有什么好处呢，我们思考一个问题$kruskal$每次加入的边都是当前最优的，而先加入的边所连的点又先合并，故在$kruskal$重构树里父亲节点一定不如儿子节点优秀。

那么我们现在再来思考这个道题，我们首先跑一遍最短路，算出每个点到$1$号节点的最小距离（不能用$SPFA$）然后建一课边权和（以海拔为边权）最大的$kruskal$最大重构树，由于父节点一定比儿子节点更劣的原则，我们找到当前节点的最高的祖宗节点满足：其海拔高度高于题目所给高度，于是这个祖宗节点的子树当前节点都可到，只需查找其中的最小距离即可。

找祖宗节点可以倍增，最小距离可以预处理，于是这道题$O(n\log n)$就做完了。

Code

#include<bits/stdc++.h>
#define LL long long
#define PII pair<long long, int>
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();}
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void out(T res)
{
    if(res > 9) out(res / 10);
    putchar(res % 10 + '0');
}
template <class T>
inline void write(T res)
{
    if(res < 0) putchar('-'), res = -res;
    out(res), putchar('\n');
}
const int N = 7e5 + 5;
int n, m, T;
LL dist[N];
namespace DFS
{
    int idx;
    int e[N << 1], ne[N << 1], h[N], w[N << 1];
    inline void add(int x, int y, int z)
    {
        idx ++;
        e[idx] = y, ne[idx] = h[x], h[x] = idx, w[idx] = z;
    }
    priority_queue<PII, vector<PII>, greater<PII>>q;
    int p[N];
    inline void dfs()
    {
        memset(p, 0, sizeof(p));
        memset(dist, 0x3f, sizeof(dist));
        dist[1] = 0;
        q.push({0, 1});
        while(!q.empty())
        {
            PII o = q.top();
            q.pop();
            if(p[o.second]) continue;
            p[o.second] = 1;
            for(int i = h[o.second], j; ~i;i = ne[i])
            {
                j = e[i];
                if(dist[j] > dist[o.second] + w[i])
                {
                    dist[j] = dist[o.second] + w[i];
                    q.push({dist[j], j});
                }
            }
        }
    }
    inline void init()
    {
        idx = 0;
        memset(h, -1, sizeof(h));
    }
}
struct Edge{
    int o, u, w;
    bool operator< (Edge b)
    {
        return w < b.w;
    }
}edge[N << 1];
int fa[N];
int idx;
int e[N << 2], ne[N << 2], h[N], w[N << 2];
inline void add(int x, int y)
{
    idx ++;
    e[idx] = y, ne[idx] = h[x], h[x] = idx;
}
inline int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int cnt;
LL val[N];
int father[N][28], depth[N];
void dfs(int x, int y)
{
    depth[x] = depth[y] + 1;
    if(x != y)
    {
        father[x][0] = y;
        for(int i = 1;i <= 27;i ++)
            father[x][i] = father[father[x][i - 1]][i - 1];
    }
    for(int i = h[x], j; ~i;i = ne[i])
    {
        j = e[i];
        if(j == y) continue;
        dfs(j, x);
        dist[x] = min(dist[x], dist[j]);
        val[x] = min(val[j], val[x]);
    }
}
int q, k, s, last;
inline LL lca(int x, int limit)
{
    for(int i = 27;i >= 0;i --) 
        if(father[x][i] && val[father[x][i]] > limit) x = father[x][i];
    return dist[x];
}
inline void query()
{
    read(q, k, s);
    int v, p;
    while(q --)
    {
        read(v, p);
        v = (LL)(v + k * last - 1) % n + 1;
        p = (LL)(p + k * last) % (s + 1);
        write(last = lca(v, p));
    }
}
inline void work()
{
    last = 0;
    DFS:: init();
    idx = 0;
    memset(h, -1, sizeof(h));
    memset(depth, 0, sizeof(depth));
    memset(val, 0, sizeof(val));
    read(n, m);
    for(int i = 1;i < N;i ++) fa[i] = i;
    for(int i = 1;i <= n;i ++) val[i] = 0x3f3f3f3f3f3f3f3f;
    cnt = n;
    for(int i = 1, o, u, v, w;i <= m;i ++)
        read(o, u, v, w), DFS:: add(o, u, v), DFS:: add(u, o, v), edge[i] = {o, u, w};
    DFS:: dfs();
    sort(edge + 1, edge + m + 1);
    for(int i = m, o, u;i >= 1;i --)
    {
        o = find(edge[i].o), u = find(edge[i].u);
        if(o == u) continue;
        cnt ++;
        val[cnt] = edge[i].w;
        fa[o] = cnt, fa[u] = cnt;
        add(o, cnt), add(cnt, o), add(u, cnt), add(cnt, u);
    }
    for(int i = n + 1;i <= cnt;i ++) dist[i] = 0x3f3f3f3f3f3f3f3f;
    dfs(cnt, cnt);
    query();
}
int main()
{
    read(T);
    while(T --) work();
    return 0;
}