「NOI 2018」归程

Description

题目链接：UOJ 393

魔力之都可以抽象成一个 $n$ 个节点、$m$ 条边的无向连通图。我们依次用 $l,a$ 描述一条边的长度、海拔。

作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。

我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。

Yazid 是一名来自魔力之都的 OIer，刚参加完 ION2018 的他将踏上归程，回到他温暖的家。

Yazid 的家恰好在魔力之都的 $1$ 号节点。对于接下来 $Q$ 天，每一天 Yazid 都会告诉你他的出发点 $v$ ，以及当天的水位线 $p$。

每一天，Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。

需要特殊说明的是，第二天车会被重置，这意味着：

车会在新的出发点被准备好。
Yazid 不能利用之前在某处停放的车。

Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。

本题 $T$ 组数据，并且强制在线。

数据范围：$T\le 3$，$n\le 2\times 10^5$，$m,Q\le 4\times 10^5$，$l\le 10^4$，$a\le 10^9$

Solution

我们先分析一下询问的本质：将 $1$ 到 $v$ 的路径分成两个部分，一段全部开始，后一段全部走路。那我们可以枚举一个断点 $u$，在满足 $u$ 到 $v$ 的路径上所有的边的海拔都大于 $p$ 的情况下，要求 $1$ 到 $u$ 的最短路最短。

我们怎么求出从 $v$ 出发可以到达的点呢？这些点显然满足从 $v$ 出发，路径上所有边的海拔都大于 $p$。由此可以想到，这些路径一定在原图的最大生成树上！

至此，已经可以发现能用 $\text{Kruskal}$ 重构树求解了。关于 $\text{Kruskal}$ 重构树的求法，请见「算法笔记」Kruskal 重构树。

我们把每条边按照海拔降序排列，求出关于海拔的最大生成树。由于这样的重构树是一个小根堆（每个节点子树内的所有节点的点权都不小于该节点），对于每次询问求出包含 $v$ 的子树中根节点深度最小并且海拔（点权）大于 $p$ 的子树 $x$，那么 $x$ 子树内的所有节点都可以由 $v$ 开车到达！

求解深度最小的满足条件的节点，可以直接用树上倍增解决，这个倍增数组可以在 $\text{Kruskal}$ 的过程中求出来。

现在，这棵子树内的所有点都可以作为上文所说的断点，我们只需要求出子树内的点到点 $1$ 的最短距离的最小值。我们可以预处理每个点到 $1$ 的最短距离，然后对于每棵子树求个 $\min$ 即可。由于重构树的求解过程中我们可以知道这棵树的形态，所以这个取 $\min$ 的过程不需要 $\text{DFS}$，而是可以直接在 $\text{Kruskal}$ 中完成！

~~UOJ 的 hack 数据很神仙啊！~~

时间复杂度：$O(T\cdot n\log n)$（此处认为 $n,m,Q$ 三者同阶）

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
typedef std::pair<int,int> pii;
#define mk std::make_pair
inline char nc() {
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
template <class Tp> inline void read(register Tp &s) {
    s=0;char c=nc();for(;c<'0'||c>'9';c=nc());for(;c>='0'&&c<='9';s=s*10+(c^48),c=nc());
}

const int N=4e5+5,M=8e5+5,logN=19+1;
int n,m,tot,lnk[N],ter[M],nxt[M],val[M],fa[N],f[N][logN],dis[N],hei[N];
bool vis[N];
struct Edge {
    int u,v,h;
    bool operator < (const Edge &rhs) const {
        return h>rhs.h;
    }
}e[M];

void add(int u,int v,int w) {
    ter[++tot]=v,nxt[tot]=lnk[u],val[tot]=w,lnk[u]=tot;
}
void input() {
    tot=0,memset(lnk,0,sizeof(lnk));
    read(n),read(m);
    for(int i=1;i<=m;++i) {
        int u,v,w,h;
        read(u),read(v),read(w),read(h);
        add(u,v,w),add(v,u,w);
        e[i].u=u,e[i].v=v,e[i].h=h;
    }
}
void dijkstra(int s) {
    memset(dis,0x7f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    std::priority_queue<pii,std::vector<pii>,std::greater<pii> > q;
    q.push(mk(dis[s]=0,s));
    while(!q.empty()) {
        int u=q.top().second; q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=lnk[u];i;i=nxt[i]) {
            int v=ter[i];
            if(dis[v]>dis[u]+val[i]) {
                dis[v]=dis[u]+val[i];
                if(!vis[v]) q.push(mk(dis[v],v));
            }
        }
    }
}
int find(int x) {
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void exKruskal() {
    std::sort(e+1,e+m+1);
    for(int i=1;i<=n+n;++i) fa[i]=i;
    int idx=n;
    for(int i=1;i<=m;++i) {
        int fu=find(e[i].u),fv=find(e[i].v);
        if(fu==fv) continue;
        fa[fu]=fa[fv]=++idx,hei[idx]=e[i].h;
        dis[idx]=std::min(dis[fu],dis[fv]);
        f[fu][0]=f[fv][0]=idx;
    }
    for(int j=1;(1<<j)<=idx;++j) for(int i=1;i<=idx;++i) f[i][j]=f[f[i][j-1]][j-1];
}
int query(int u,int p) {
    for(int i=19;~i;--i) if(f[u][i]&&hei[f[u][i]]>p) u=f[u][i];
    return dis[u];
}
void solve() {
    int q,k,s;
    read(q),read(k),read(s);
    int lastans=0;
    while(q--) {
        int v,p;
        read(v),read(p);
        v=(v+k*lastans-1)%n+1;
        p=(p+1LL*k*lastans)%(s+1);
        printf("%d\n",lastans=query(v,p));
    }
}
int main() {
    int T;
    for(scanf("%d",&T);T--;) {
        input();
        dijkstra(1);
        exKruskal();
        solve();
    }
    return 0;
}