P4768 [NOI2018]归程

看了这道题才知道有**Kruskal重构树**这种算法 下面是对它的一些介绍 顾名思义，Kruskal重构树是基于Kruskal的一种算法 它可以处理“从某点出发经过不超过w的边权能到达的最远距离” “从x到y所有路径的最大边权最小值”等问题 _构建_ ：按照边权从大到小排序，通过给两个联通块新建一个权值为边权的共同父亲，表示在它们之间连一条边。也是用并查集实现。 _ 性质_ ： - 树上的非叶子节点表示生成树上的一条边，叶子结点表示生成树上的点 - 对于非叶子节点，它的权值一定小于它父亲的权值 - 原树两点间路径边权最大值等于重构树中两点间路径点权最大值。 - 任意一个非叶子节点的子树中所有的叶子节点中，任意两个节点在原树中路径上边权最大值小于等于这个非叶子节点的点权 - 它的本质是一个二叉堆 ------------ 对于这道题也是类似的 把边按照海拔高度从大到小排序 构建Kruskal重构树 然后从最后一个节点开始dfs整棵树 处理出1~n号节点的dfs序，以及每个点的倍增数组 其中$d[i][j]$表示从i开始跳$2^j$步的最小海拔高度 对于每个询问，先让询问节点跳到不积水的最远的地方 答案就是它的子树中到1的最短路 可以用线段树维护 注意求最短路要用堆优化dijkstra，因为spfa死了 ``` #include<cstdio> #include<cstring> #include<cctype> #include<queue> #include<algorithm> #define reg register #define reset(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int N=2e5+5,M=4e5+5,inf=1e9; struct node { int to,nxt,dis,het; }edge[M<<1]; struct E { int from,to,dis,het; inline friend bool operator < (E a,E b) {return a.het>b.het;} }e[M]; struct P { int x; ll d; inline friend bool operator < (P a,P b) {return a.d>b.d;} }; int n,m,head[M],num,tim,fa[M],Q,K,S; int cnt,L[M],R[M],a[M],f[M][20],d[M][20]; ll dis[N],ans,tmin[N<<2]; bool vis[N]; priority_queue<P>q; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void clear(){reset(head); num=0; tim=0; ans=0;} inline void add_edge(int from,int to,int dis,int het) { edge[++num]=(node){to,head[from],dis,het}; head[from]=num; } int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} inline void Dijkstra() { memset(dis,127/3,sizeof(dis)); memset(vis,0,sizeof(vis)); q.push((P){1,0}); dis[1]=0; while (!q.empty()) { P u=q.top(); q.pop(); if (u.d!=dis[u.x]||vis[u.x]) continue; vis[u.x]=1; for (reg int i=head[u.x];i;i=edge[i].nxt) { int v=edge[i].to,d=edge[i].dis; if (dis[v]>dis[u.x]+d) q.push((P){v,u.d+d}),dis[v]=u.d+d; } } } inline void Kruskal() { for (reg int i=1,tt=0;i<=m;i++) { int x=find(e[i].from),y=find(e[i].to); if (x==y) continue; ++tt; ++cnt; add_edge(cnt,x,e[i].dis,e[i].het); add_edge(cnt,y,e[i].dis,e[i].het); fa[cnt]=fa[x]=fa[y]=cnt; if (tt==n-1) break; } } void dfs(int k) { if (k<=n) L[k]=++tim,a[tim]=k; else L[k]=inf; for (reg int j=1;j<=19;j++) { f[k][j]=f[f[k][j-1]][j-1]; d[k][j]=min(d[k][j-1],d[f[k][j-1]][j-1]); } for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to,h=edge[i].het; f[v][0]=k; d[v][0]=h; dfs(v); L[k]=min(L[k],L[v]); } R[k]=tim; } inline int getpos(int x,int h) { for (reg int i=19;~i;i--) if (f[x][i]&&d[x][i]>h) x=f[x][i]; return x; } inline void pushup(int now){tmin[now]=min(tmin[now<<1],tmin[now<<1|1]);} void build(int l,int r,int now) { if (l==r) {tmin[now]=dis[a[l]]; return;} int mid=(l+r)>>1; build(l,mid,now<<1); build(mid+1,r,now<<1|1); pushup(now); } ll query(int L,int R,int l,int r,int now) { if (l>R||r<L) return inf; if (l>=L&&r<=R) return tmin[now]; int mid=(l+r)>>1; if (mid>=R) return query(L,R,l,mid,now<<1); if (mid<L) return query(L,R,mid+1,r,now<<1|1); return min(query(L,mid,l,mid,now<<1),query(mid+1,R,mid+1,r,now<<1|1)); } inline void work() { clear(); cnt=n=read(),m=read(); for (reg int i=1;i<=m;i++) { int x=read(),y=read(),z=read(),h=read(); e[i]=(E){x,y,z,h}; add_edge(x,y,z,h); add_edge(y,x,z,h); } sort(e+1,e+m+1); for (reg int i=1;i<=n;i++) fa[i]=i; Dijkstra(); clear(); Kruskal(); dfs(cnt); build(1,n,1); Q=read(),K=read(),S=read(); while (Q--) { int v=(ll)(K*ans+read()-1)%n+1; int p=(ll)(K*ans+read())%(S+1); v=getpos(v,p); ans=query(L[v],R[v],1,n,1); printf("%lld\n",ans); } } int main() { // freopen("return.in","r",stdin); // freopen("return.out","w",stdout); for (int T=read();T;T--) work(); return 0; } ```