kruskal重构树

2023-09-22 13:44:21

Kruskal重构树

第二次学了。
大致思路就是在最小生成树加边的时候，把每条边也设一个点，和他连着的两个点连边。由于最小生成树的贪心，感觉很像哈夫曼树，有性质是经过的边的长度（已经转化为点权）越向上越大/越小，取决于生成树的排序。那就可以通过倍增找不经过长度超过x的边所能走到的所有点，实际上是一直往上跳的那个子树。

		for (int i=1;i<=n;i++) bel[i]=i,top[i]=i;
		int num=n;
		for (int i=1;i<=m;i++)
		{
			int f1=find(edges[i].u),f2=find(edges[i].v);
			if (f1==f2) continue;
			++num;
			bel[f1]=f2;
			addedge(num,top[f1],edges[i].a);
			addedge(num,top[f2],edges[i].a);
			top[f2]=num;
		}

bel是并查集的fa，top是这一坨联通块现在的最上面的那个代表边的点的编号。fa正常合并，每次把top改成“新建的那个代表边的点”，再加边就向这个点连边即可。

题：NOI2018归程
题目链接
大意：每条边有一个海拔，多组询问，每次询问给出 v , p v,p v,p，海拔高于 p p p的边没有长度，问从 v v v号点走到 1 1 1号点的最短路。
思路：根据重构树的性质，做最大生成树，他的重构树保证越向上海拔越小，从 v v v倍增向上跳，一直跳到海拔小于 p p p，那么实际上能“免费”走到的点就应该是能向上跳的最顶上的点的那个子树。维护子树mindis即可。

#include<bits/stdc++.h>
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

inline ll read()
{
	ll f=1,sum=0;char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-1;c=getchar();}
	while (isdigit(c)) {sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}
const int MAXN=500010;
const int MAXM=1000010;
struct Node{
	int u,v,a,l;
	bool operator < (const Node b) const {return a>b.a;}
}edges[MAXM];
int bel[MAXN],top[MAXN];
int find(int x)
{
	if (bel[x]!=x) bel[x]=find(bel[x]);
	return bel[x];
}
struct edge{
	int next,to,val;
}e[MAXM*2];
int head[3*MAXN],cnt;
void addedge(int u,int v,int w)
{
	e[++cnt].next=head[u];
	e[cnt].to=v;
	e[cnt].val=w;
	head[u]=cnt;
}
int dis[MAXN];
priority_queue <pa,vector<pa>,greater<pa> > q;
bool vis[MAXN];
void Dijkstra(int n)
{
	for (int i=1;i<=n;i++) dis[i]=INT_MAX,vis[i]=0;
	dis[1]=0;
	q.push(mp(0,1));
	while (!q.empty())
	{
		int x=q.top().se;
		q.pop();
		if (vis[x]) continue;
		vis[x]=1;
		for (int i=head[x];i;i=e[i].next)
		{
			int v=e[i].to;
			if (dis[v]>dis[x]+e[i].val) dis[v]=dis[x]+e[i].val,q.push(mp(dis[v],v));
		}
	}
}
const int LOG=25;
int f[MAXN][LOG],g[MAXN][LOG];
int mn[MAXN];
void dfs(int x,int n)
{
	if (x<=n) mn[x]=dis[x];
	else mn[x]=INT_MAX;
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		g[v][0]=e[i].val;
		f[v][0]=x;
		dfs(v,n);
		mn[x]=min(mn[x],mn[v]);
	}
}
int main()
{
	int T=read();
	while (T--)
	{
		memset(head,0,sizeof(head));
		cnt=0;
		int n=read(),m=read();
		for (int i=1;i<=m;i++) 
		{
			edges[i].u=read(),edges[i].v=read(),edges[i].l=read(),edges[i].a=read();
			addedge(edges[i].u,edges[i].v,edges[i].l);
			addedge(edges[i].v,edges[i].u,edges[i].l);
		}
		Dijkstra(n);
		memset(head,0,sizeof(head));
		cnt=0;
		sort(edges+1,edges+1+m);
		for (int i=1;i<=n;i++) bel[i]=i,top[i]=i;
		int num=n;
		for (int i=1;i<=m;i++)
		{
			int f1=find(edges[i].u),f2=find(edges[i].v);
			if (f1==f2) continue;
			++num;
			bel[f1]=f2;
			addedge(num,top[f1],edges[i].a);
			addedge(num,top[f2],edges[i].a);
			top[f2]=num;
		}
		dfs(num,n);
		f[num][0]=num;
		for (int j=1;j<LOG;j++) for (int i=1;i<=num;i++) f[i][j]=f[f[i][j-1]][j-1];
		for (int j=1;j<LOG;j++) for (int i=1;i<=num;i++) g[i][j]=g[f[i][j-1]][j-1];
		// for (int i=1;i<=num;i++,cout<<endl) for (int j=0;j<3;j++) cout<<f[i][j]<<' ';
		int q=read(),k=read(),s=read();
		int lastans=0;
		while (q--)
		{
			int v0=read(),p0=read();
			int v=(1ll*v0+1ll*k*lastans-1)%n+1;
			int p=(1ll*p0+1ll*k*lastans)%(s+1);
			// cout<<v<<"--"<<endl;
			for (int i=LOG-1;i>=0;i--)
				if (g[v][i]>p) v=f[v][i];//cout<<v<<' '<<i<<' '<<f[v][i]<<' '<<g[v][i]<<endl;
			// cout<<v<<endl;
			lastans=mn[v]; 
			cout<<lastans<<'\n';
		}
	}
	return 0;
}

题：洛谷P7834 [ONTAK2010] Peaks 加强版
题目链接
大意：无向图，强制在线多组询问从 u u u点出发不经过权值 > x > x >x的边，能走到的点的点权第 k k k大是多少。
思路：重构树+倍增向上跳找到子树根，转化为求子树根的第 k k k大，经典dfs序上主席树。

#include<bits/stdc++.h>
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

inline ll read()
{
	ll f=1,sum=0;char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-1;c=getchar();}
	while (isdigit(c)) {sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}
const int MAXN=300010;
const int MAXM=1000010;
struct edge{
	int next,to;
}e[MAXM*4];
int head[MAXN],cnt;
void addedge(int u,int v)
{
	e[++cnt].next=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}
struct Node{
	int u,v,w;
	bool operator < (const Node b) const {return w<b.w;}
}edges[MAXM];
int a[MAXN],fa[MAXN],top[MAXN],val[MAXN];
int find(int x)
{
	if (fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}
const int LOG=25;
int sz[MAXN],f[MAXN][LOG],g[MAXN][LOG],l[MAXN],r[MAXN];
int tots;
struct Point{
	int lch,rch,val;
}tr[MAXN*LOG];
int root[MAXN],treenum;
int modify(int pre,int left,int right,int x)
{
	int now=++treenum;
	if (left==right)
	{
		tr[now].lch=tr[now].rch=0;
		tr[now].val=tr[pre].val+1;
		return now;
	}
	int mid=(left+right)>>1;
	if (x<=mid)
	{
		tr[now].lch=modify(tr[pre].lch,left,mid,x);
		tr[now].rch=tr[pre].rch;
	}
	else
	{
		tr[now].lch=tr[pre].lch;
		tr[now].rch=modify(tr[pre].rch,mid+1,right,x);
	}
	tr[now].val=tr[tr[now].lch].val+tr[tr[now].rch].val;
	return now;
}
int query(int root1,int root2,int left,int right,int k)
{
	if (left==right) return left;
	int mid=(left+right)>>1;
	if (tr[tr[root2].lch].val-tr[tr[root1].lch].val>=k) return query(tr[root1].lch,tr[root2].lch,left,mid,k);
	else return query(tr[root1].rch,tr[root2].rch,mid+1,right,k-tr[tr[root2].lch].val+tr[tr[root1].lch].val);
}
void dfs_order(int x,int n)
{
	if (x<=n)
	{
		l[x]=r[x]=++tots;
		root[tots]=modify(root[tots-1],1,n,a[x]);
		return ;
	}
	int i=head[x];
	dfs_order(e[i].to,n);
	l[x]=l[e[i].to];
	i=e[i].next;
	dfs_order(e[i].to,n);
	r[x]=r[e[i].to];
}
void dfs(int x)
{
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		f[v][0]=x,g[v][0]=val[x];
		dfs(v);
		sz[x]+=sz[v];
	}
	if (!sz[x]) sz[x]=1;
}
vector <int> vals;
int main()
{
	int n=read(),m=read(),q=read();
	for (int i=1;i<=n;i++) a[i]=read(),vals.push_back(a[i]);
	sort(vals.begin(),vals.end());
	int newsize=unique(vals.begin(),vals.end())-vals.begin();
	vals.resize(newsize);
	for (int i=1;i<=n;i++) a[i]=lower_bound(vals.begin(),vals.end(),a[i])-vals.begin()+1;
	for (int i=1;i<=m;i++) edges[i].u=read(),edges[i].v=read(),edges[i].w=read();
	sort(edges+1,edges+1+m);
	for (int i=1;i<=n;i++) fa[i]=i,top[i]=i;
	int num=n;
	for (int i=1;i<=m;i++)
	{
		int f1=find(edges[i].u),f2=find(edges[i].v);
		if (f1==f2) continue;
		++num;
		fa[f1]=f2;
		addedge(num,top[f1]),addedge(num,top[f2]);
		// cout<<f1<<" "<<f2<<" "<<num<<' '<<top[f1]<<" "<<top[f2]<<endl;
		val[num]=edges[i].w;
		top[f2]=num;
	}
	dfs(num);
	f[num][0]=num,g[num][0]=val[num];
	// for (int i=1;i<=num;i++) cout<<i<<' '<<sz[i]<<endl;
	for (int j=1;j<LOG;j++) for (int i=1;i<=num;i++) f[i][j]=f[f[i][j-1]][j-1];
	for (int j=1;j<LOG;j++) for (int i=1;i<=num;i++) g[i][j]=g[f[i][j-1]][j-1];
	// for (int i=1;i<=num;i++,cout<<endl) for (int j=0;j<5;j++) cout<<f[i][j]<<' ';
	int lstans=0;
	dfs_order(num,n);
	while (q--)
	{
		int _u=read(),_x=read(),_k=read();
		int u=(_u^lstans)%n+1,x=_x^lstans,k=(_k^lstans)%n+1;
		for (int j=LOG-1;j>=0;j--) if (g[u][j]<=x) u=f[u][j];
		if (sz[u]<k)
		{
			cout<<"-1\n";
			lstans=0;
			continue;
		}
		k=sz[u]-k+1;
		int ret=query(root[l[u]-1],root[r[u]],1,n,k);
		lstans=vals[ret-1];
		cout<<lstans<<'\n';
	}
	return 0;
}
更多推荐

【计算机网络】IP协议

文章目录TCP与IP之间的关系IP地址的认识协议报头格式1.报头和有效载荷如何分离？2.8位协议3.4位版本4.8位服务类型5.16位总长度6.8位生存时间TTL网段划分IP地址的划分子网划分CIDR的提出如何理解CIDRTCP与IP之间的关系如：假设你上高中时，班里有个同学叫张三，他的老爹是学校的校长你感觉每次考试都

微前端qiankun简易上手指南

微前端架构一、什么是微前端架构微前端是一种多个团队通过独立发布功能的方式来共同构建现代化web应用的技术手段及方法策略。微前端借鉴了微服务的架构理念，将一个庞大的前端应用才分为多个独立灵活的小型应用，每个应用都可以独立开发，独立运行，独立部署，再将这些小型应用联合为一个完整的应用。微前端既可以将多个项目融合为一，又可以

Pixea Plus for Mac：极简图片浏览，高效图片管理

在处理和浏览图片时，我们往往需要一个得心应手的工具，尤其是当你的图片库包含了各种不同格式，例如JPEG、HEIC、psd、RAW、WEBP、PNG、GIF等等。今天，我们要推荐的，就是一款极简、高效的Mac图片浏览和管理工具——PixeaPlus。PixeaPlusMac版是一款专为Mac用户设计的图片浏览器和管理工具

【Linux】自动化构建工具 —— make/makefile&&Linux第一个小程序 - 进度条

​​📝个人主页：@Sherry的成长之路🏠学习社区：Sherry的成长之路（个人社区）📖专栏链接：Linux🎯长路漫漫浩浩，万事皆有期待上一篇博客：Linux编译器gcc/g++的使用&&初识动静态链接库文章目录一、前言二、概念三、代码实现四、实现原理1、依赖关系和依赖方法2、清理①.PHONY伪目标②.PHO

ZABBIX 6.4安装部署

ZABBIX6.4安装部署zabbix的主要组成：1、ZabbixServer6.4：Zabbix服务端，是Zabbix的核心组件。它负责接收监控数据并触发告警，还负责将监控数据持久化到数据库中。2、ZabbixAgent：Zabbix客户端，部署在被监控设备上，负责采集监控数据，采集后的数据发送给ZabbixServ

林木种苗生产vr虚拟实训教学降低培训等待周期

林业种植管理在保护水土流失、气候变化及经济社会发展中发挥重要的作用，林业教学往往需要进入林区进行实操察验，在安全性、时间及效率上难以把控，因此有更多林业畜牧院校创新性地引进VR虚拟现实技术。在林业领域，实地调查是获取准确数据和深入了解森林生态的重要手段。然而，传统的实地调查方法存在诸多问题，如时间成本高、人力物力投入大

每天一个面试题之类加载机制、spirngboot的启动机制

jvm类加载机制Java虚拟机（JVM）的类加载机制是Java的关键部分，它负责加载、链接和初始化类。类加载机制的主要任务是将Java类的字节码文件转换为可以在JVM上执行的运行时数据结构。这个过程包括以下三个主要步骤：加载（Loading）：在此阶段，类加载器负责查找并加载类的字节码文件。这个过程通常从类路径（Cla

搭建私人图床结合内网穿透实现公网访问，让您的摄影作品连接世界

文章目录1.树洞外链网站搭建1.1下载安装树洞外链1.2树洞外链网页测试1.3cpolar的安装和注册2.本地网页发布2.1Cpolar临时数据隧道2.2Cpolar稳定隧道（云端设置）2.3Cpolar稳定隧道（本地设置）3.公网访问测试社交平台具有庞大的用户基础和活跃的社交功能，我们将图片发布到社交平台可以让照片更

Learn Prompt-ChatGPT 精选案例:内容总结

ChatGPT可以通过分析内容并生成一个浓缩版本来总结文本。这对节省时间和精力很有帮助，特别是在阅读长篇文章、研究论文或报告时。通用总结​你所要做的就是把具体的文字复制并粘贴到提示中，并要求ChatGPT对所选文本进行简化总结。这里我们参考openai官网提供的例子Summarizefora2ndgrader来总结一下

想学嵌入式开发，薪资怎么样？

想学嵌入式开发，薪资怎么样？对于嵌入式工程师来说呢，它重点学习内容就是首先一定要打好基础，如果从编程语言角度来讲，那么可以在语言上选C或者C++，你可以选择其中任何一门语言作为你的入门。最近很多小伙伴找我，说想要一些嵌入式机学习资料，然后我根据自己从业十年经验，熬夜搞了几个通宵，精心整理了一份「嵌入式入门到高级教程+工

思腾云计算

全新一代的Atlas是支持ARM架构和X86架构的，像Intel，AMD，海光，鲲鹏，飞腾的CPU都支持。Atlas300IPro，是基于昇腾310芯片开发推理卡，最高功耗72W，被动散热，半高半长单宽，达芬奇架构，作为推理卡需求比较简单，算力和显存平衡就可，所以它支持FP16*70TFLOPS和INT8*140TOP

热文推荐
  1. 红海云签约科百特，“膜界”小巨人人力资源数字化转型全面提速

    杭州科百特过滤器材有限公司（以下简称“科百特”）是全球优秀的创新过滤企业，专注于纳米膜材料的开发和应用，致力于为全球集成电路制造和生物制药产业提供创新的过滤纯化解决方案。近日，科百特与广州红海云计算股份有限公司达成战略合作。红海云作为一家技术驱动的专业型厂商，基于深厚的人力资源管理专业积累和前沿的数字技术，成功打造了众

  2. Linux CentOS7系统运行级别

    运行级别就是Linux操作系统当前正在运行的功能级别。在早期系统设置中，共设有七个运行级别，编号从0到6。系统可以引导到任何给定的运行级别。每个运行级别指定不同的系统配置，并允许访问不同的进程组合。默认情况下，Linux会引导至运行级别3或运行级别5。启动时一次只执行一个运行级别，它不会一个接一个地执行。在SysVin

  3. Buffer Pool

    一.BufferPool的含义BufferPool：缓冲池，简称BP，其作用是用来缓存表数据与索引数据，减少磁盘IO操作，提升效率。当Mysql执行查询的sql语句的时候，会先去缓存当中看是否有对应的数据，如果有则直接读内存，如果没有则去磁盘里拿，然后把数据放到BufferPool里拿，来提高查询速度。BufferPo

  4. Unity减少发布打包文件的体积——获取精灵图片的信息限制它的大小

    一、起因一个工程，打包成webGL且压缩成zip文件后，接近400M，后来把大的精灵图片设置最大尺寸，降低大小后，再次发布，zip文件缩减到250M二、如何一键获得工程里面的精灵图片信息三、获取精灵图片信息1、查找项目中的所有精灵图片//查找工程文件中的所有精灵图片string[]guids=AssetDatabase

  5. 2023年中秋·国庆节放假通知

    放假期间如有业务、技术及其他相关需求，欢迎新老客户前来咨询！放假期间如给您带来不便敬请谅解!注意事项1、放假离开公司前须全面清扫所属办公区域的卫生，收拾好桌面、保管好个人办公物品；2、关闭个人电脑等办公设备的电源，切断用电设备的插座电源开关，锁好门窗防雨，做好防火防盗工作；3、节日期间重点安全部门，如仓库，要加强对仓库

  6. 【计算机网络】网络编程接口 Socket API 解读（5）

    Socket是网络协议栈暴露给编程人员的API，相比复杂的计算机网络协议，API对关键操作和配置数据进行了抽象，简化了程序编程。本文讲述的socket内容源自Linuxman。本文主要对各API进行详细介绍，从而更好的理解socket编程。connectconnect()遵循POSIX.1-20081.库标准c库，li

  7. IP归属地应用的几个主要特点

    作为一款优秀的IP地址定位工具，主题IP归属地的应用无疑是最好的选择之一。该应用可以将您需要查询的IP地址快速定位到所在的具体物理位置，并提供详细的地址和地图信息。接下来，让我们一起来看一看IP归属地应用的几个主要特点：1.快速查询IP地址归属地主题IP归属地应用的查询速度非常快，您只需要输入需要查询的IP地址点击“查

  8. 微软宣布推广数字助理 Copilot；GPT 应用开发和思考

    🦉AI新闻🚀微软宣布推广基于生成式人工智能的数字助理Copilot摘要：微软宣布将基于生成式人工智能的数字助理Copilot推广到更多软件产品中。新的AI助理MicrosoftCopilot将在Windows中无缝可用，包括Windows11桌面、Microsoft365、Outlook、Edge浏览器和必应。它能

  9. 【Linux网络编程】序列化与反序列化

    我们网络收发数据实际上只能接收到字符串，但是在现实生活中描述一个客观物体都是以很多属性来描述的，所以在网络中结构体类型的数据更常见，那我们如何发送结构体数据呢？这里就涉及到协议的概念了。我们想象一个场景，在特种兵执行任务时，他们有特定的战术手语，这样他们就能根据手语进行相应的战术配合了。所以协议也是一样，客户端和服务器