洛谷 P4768 [NOI2018]归程 题解【Kruskal重构树】【倍增】

点击量：497

学习了一下重构树。

目录

题目背景

本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。

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

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

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

题目描述

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

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

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

• 需要特殊说明的是，第二天车会被重置，这意味着：
  • 车会在新的出发点被准备好。
  • Yazid 不能利用之前在某处停放的车。

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

本题的部分测试点将强制在线，具体细节请见【输入格式】和【子任务】。

输入格式

从文件 return.in 中读入数据。

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

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

• 第一行 $ 2$ 个非负整数 $ n,m$，分别表示节点数、边数。
• 接下来 $ m$ 行，每行 $ 4$ 个正整数 $ u,v,l,a$，描述一条连接节点 $ u,v$ 的、长度为 $ l$、海拔为 $ a$ 的边。
  • 在这里，我们保证 $ 1≤u,v≤n$。
• 接下来一行 $ 3$ 个非负数 $ Q,K,S$，其中 $ Q$ 表示总天数，$ K\in{0,1}$ 是一个会在下面
  被用到的系数， $ S$ 表示的是可能的最高水位线。
• 接下来 $ Q$ 行依次描述每天的状况。每行 $ 2$ 个整数 $ v_0,p_0$ 描述一天：
  • 这一天的出发节点为 $ v=(v_0+K\times lastans – 1) \bmod n+1$。
  • 这一天的水位线为 $ p=(p_0+K\times lastans) \bmod (S + 1)$。
  • 其中 $ lastans$ 表示上一天的答案（最小步行总路程）。特别地，我们规定第 $ 1$ 天时 $ lastans=0$。
  • 在这里，我们保证 $ 1\le v_0\le n， 0\le p_0\le S$。

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

输出格式

输出到文件 return.out 中。
依次输出各组数据的答案。对于每组数据：

• 输出 $ Q$ 行每行一个整数，依次表示每天的最小步行总路程。

输入输出样例

【样例 1 输入】

1
4 3
1 2 50 1
2 3 100 2
3 4 50 1
5 0 2
3 0
2 1
4 1
3 1
3 2

【样例 1 输出】

0
50
200
50
150 

【样例 1 解释】
第一天没有降水，Yazid 可以坐车直接回到家中。

第二天、第三天、第四天的积水情况相同，均为连接 $ 1,2$ 号节点的边、连接 $ 3,4$ 号
点的边有积水。

对于第二天， Yazid 从 $ 2$ 号点出发坐车只能去往 $ 3$ 号节点，对回家没有帮助。因此 Yazid 只能纯靠徒步回家。

对于第三天，从 $ 4$ 号节点出发的唯一一条边是有积水的，车也就变得无用了。 Yazid 只能纯靠徒步回家。

对于第四天， Yazid 可以坐车先到达 $ 2$ 号节点，再步行回家。

第五天所有的边都积水了，因此 Yazid 只能纯靠徒步回家。

【样例 2 输入】

1
5 5
1 2 1 2
2 3 1 2
4 3 1 2
5 3 1 2
1 5 2 1
4 1 3
5 1
5 2
2 0
4 0

【样例 2 输出】

0 
2 
3 
1

【样例 2 解释】

本组数据强制在线。

第一天的答案是 $ 0$，因此第二天的 $ v=(5+0-1) \bmod 5+1=5$，$ p=(2+0) \bmod (3+1)=2$。

第二天的答案是 $ 2$，因此第三天的 $ v=(2+2-1) \bmod 5+1=4$，$ p=(0+2) \bmod (3+1)=2$。

第三天的答案是 $ 3$，因此第四天的 $ v=(4+3-1) \bmod 5+1=2$，$ p=(0+3) \bmod (3+1)=3$。

子任务

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

• $ n\le 2\times 10^5$，$ m\le 4\times 10^5​$，$ Q\le 4\times 10^5$，$ K\in{0,1}$，$ 1\le S\le 10^9​$。
• 对于所有边： $ l\le 10^4$，$ a\le 10^9$。
• 任意两点之间都直接或间接通过边相连。

为了方便你快速理解，我们在表格中使用了一些简单易懂的表述。在此，我们对这些内容作形式化的说明：

• 图形态：对于表格中该项为“一棵树”或“一条链”的测试点，保证 $ m=n-1$。
  除此之外，这两类测试点分别满足如下限制：
  • 一棵树：保证输入的图是一棵树，即保证边不会构成回路。
  • 一条链：保证所有边满足 $ u+1=v$。
• 海拔：对于表格中该项为“一种”的测试点，保证对于所有边有 $ a=1$。

• 强制在线：对于表格中该项为“是”的测试点，保证 $ K=1$；如果该项为“否”，则有 $ K=0$。

• 对于所有测试点，如果上述对应项为“不保证”，则对该项内容不作任何保证。

$ n$	$ m$	$ Q\le$	测试点	图形态	海拔	强制在线
$ \le 1$	$ \le 0$	$ 0$	1	不保证	一种	否
$ \le 6$	$ \le 10$	$ 10$	2
$ \le 50$	$ \le 150$	$ 100$	3
$ \le 100$	$ \le 300$	$ 200$	4
$ \le 1500$	$ \le 4000$	$ 2000$	5
$ \le 200000$	$ \le 400000$	$ 100000$	6
$ \le 1500$	$ =n-1$	$ 2000$	7	一条链	不保证
			8
			9
$ \le 200000$		$ 100000$	10	一棵树
			11			是
	$ \le 400000$		12	不保证		否
			13
			14
$ \le 1500$	$ \le 4000$	$ 2000$	15			是
			16
$ \le 200000$	$ \le 400000$	$ 100000$	17
			18
		$ 400000$	19
			20

题解：

重构树可以在这篇博客(by 守望)里学习（因为整体架构比较简单我就没写学习笔记……）

这个题是要求每天走的边大于一个值 $ S$。因此我们先把边按海拔从大到小排序。

然后对于每条连接不同联通块的边，新建一个点，点权为这条边边权，与这条边的两个点相连。

这样连出来的一定是一棵树，并且最后新建的点是根。

此时随着深度变大，点权非严格递减。因此当询问 $ S$ 时可以倍增出当前点 $ v$ 的祖先中深度最浅的满足点权 $ > S$ 的点。

进行这一步操作前需要对重构树dfs一遍，存下以每个点为根，子树中到 $ 1$ 号节点距离最近的点，答案就是这个距离。

距离直接从 $ 1$ 号点出发跑一遍 dijkstra 即可。（SPFA会被卡（甚至已经是梗了）

Code：

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using std::priority_queue;
struct Edge
{
    int u,v,w,x;
    Edge(int u,int v,int w)
    {
        this->u=u;
        this->v=v;
        this->w=w;
    }
    Edge(){}
    friend bool operator <(Edge a,Edge b)
    {return a.w>b.w;}
}E[400100];
struct edge
{
    int n,nxt,v;
    edge(int n,int nxt,int v)
    {
        this->n=n;
        this->nxt=nxt;
        this->v=v;
    }
    edge(){}
}e[800100];
int head[400100],ecnt=-1;
void add(int from,int to,int v)
{
    e[++ecnt]=edge(to,head[from],v);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to],v);
    head[to]=ecnt;
}

struct sta
{
    int n,dis;
    sta(int n,int dis)
    {
        this->n=n;
        this->dis=dis;
    }
    sta(){}
    friend bool operator <(sta a,sta b)
    {
        return a.dis>b.dis;
    }
};
int dis[400100];
int s[400100],scnt;
int Find(int x)
{
    if(s[x]==x)
        return x;
    return s[x]=Find(s[x]);
}
void Union(int x,int y)
{
    s[Find(y)]=Find(x);
}
int F[20][400100],h[400100];
void dfs(int x,int from)
{
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=from)
        {
            dfs(e[i].n,x);
            dis[x]=dis[x]<dis[e[i].n]?dis[x]:dis[e[i].n];
        }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(head,-1,sizeof(head));
        memset(dis,0x3f,sizeof(dis));
        ecnt=-1;
        int n,m,Q,k,u,v,w,x,lstans=0;
        scanf("%d%d",&n,&m);
        scnt=n;
        for(int i=1;i<=n+n-1;++i)
            s[i]=i;
        for(int i=1;i<=m;++i)
        {
            scanf("%d%d%d%d",&u,&v,&w,&x);
            E[i]=Edge(u,v,x);
            add(u,v,w);
        }
        std::sort(E+1,E+1+m);
        priority_queue<sta> q;
        dis[1]=0;
        q.push(sta(1,0));
        while(!q.empty())
        {
            sta k=q.top();
            q.pop();
            if(k.dis>dis[k.n])
                continue;
            for(int i=head[k.n];~i;i=e[i].nxt)
                if(dis[e[i].n]>k.dis+e[i].v)
                {
                    dis[e[i].n]=k.dis+e[i].v;
                    q.push(sta(e[i].n,dis[e[i].n]));
                }
        }
        memset(head,-1,sizeof(head));
        ecnt=-1;
        for(int i=1;i<=m&&scnt<n+n-1;++i)
        {
            int U=Find(E[i].u),V=Find(E[i].v);
            if(U!=V)
            {
                ++scnt;
                Union(scnt,U);
                Union(scnt,V);
                F[0][U]=scnt;
                F[0][V]=scnt;
                add(U,scnt,1);
                add(V,scnt,1);
                h[scnt]=E[i].w;
            }
        }
        F[0][scnt]=scnt;
        dfs(scnt,scnt);
        for(int i=1;i<=18;++i)
            for(int j=1;j<=scnt;++j)
                F[i][j]=F[i-1][F[i-1][j]];
        scanf("%d%d%d",&Q,&k,&w);
        for(int i=1;i<=Q;++i)
        {
            scanf("%d%d",&u,&v);
            u=(u+k*lstans-1)%n+1;
            v=(v+k*lstans)%(w+1);
            for(int j=18;j>=0;--j)
                if(h[F[j][u]]>v)
                    u=F[j][u];
            lstans=dis[u];
            printf("%d\n",lstans);
        }
    }
    return 0;
}