首页 > 其他分享 >虚树学习笔记

虚树学习笔记

时间:2023-05-31 18:13:36浏览次数:52  
标签:top 笔记 虚树 学习 建边 lca st 节点

概念

虚树是一棵树,相对于原树而言。它删去原树上某些点,再按原树父子关系连边构成的树。

它对树上算法有一定优化。假如一个树上问题仅与部分节点有关,如树形DP,DP值仅在部分节点有改变,那么就可以已这部分节点建成虚树,省略其他部分,复杂度为部分节点总和。

例:消耗战

本题的删边DP只与一点到顶点的最小边权边有关,但是要保证每个关键点的祖先都被计算。建虚树并DP是很好的选择。

建法

首先虚树保留关键点和所有他们的 lca,包括 lca 的 lca。发现两个关键点之间可能中途插入点。所以使用栈,反转扫描和建边的过程。

整个过程先将节点按dfn序排序,保证栈内存储节点在一条链上。若下一节点不在同一链上,则开始从栈顶删点直到栈次顶与当前节点在一条链上,注意弹出时要和次顶建边。此时栈顶向当前点与其的 lca 建边并弹出。现在的栈顶要么是刚才建边的 lca,就可以不管。否则就要压入建边的 lca 以保证两点 lca 有边。

int st[1000001];
vector<edge> f[1000001];
void btxs()
{
	int top=0;
	st[++top]=1;
	for(int i=1;i<=k;i++)
	{
		int lca=getlca(st[top],din[i]);
		while(dfn[st[top]]>=dfn[lca]&&top>1)
		{
			if(dfn[st[top-1]]<dfn[lca]) break;
			f[st[top-1]].push_back((edge){st[top],0/*边权*/});
			top--;
		}
		if(lca==st[top])
		{
			st[++top]=din[i];
		}
		else
		{
			f[lca].push_back((edge){st[top],0});
			top--;
			st[++top]=lca;
			st[++top]=din[i];
		}
	}
	while(top>1)
	{
		f[st[top-1]].push_back((edge){st[top],0});
		top--;
	}
}

标签:top,笔记,虚树,学习,建边,lca,st,节点
From: https://www.cnblogs.com/lizhous/p/17446948.html

相关文章

  • UART-UART非常见波特率调试应用笔记
    UART非常见波特率调试应用笔记串口通信中的波特率选择,对于确保可靠的数据传输至关重要。波特率是衡量单位时间内传输的比特数,常见的波特率包括300、1200、2400、9600、115200等。不同波特率适用于不同的应用场景和通信要求。较低的波特率适用于较长的通信距离或对传输速度要求不高......
  • 【Netty实战】1~3章学习笔记
    1.Netty总体结构1.1Netty简介​ Netty是一款用于创建高性能网络应用程序的高级框架。它的基于JavaNIO的异步的和事件驱动的实现,保证了高负载下应用程序性能的最大化和可伸缩性。​ 其次,Netty也包含了一组设计模式,将应用程序逻辑从网络层解耦,简化了开发过程,同时也最大限度......
  • uniapp专题学习(三)
    前言在uniapp专题学习(二)中学习到的知识点有viedo组件、form表单组件、navigator路由跳转以及page.json中的tabBar配置。vue语法之计算属性computed每一个计算属性都包含一个getter和一个setter,默认是利用getter来读取。所有getter和setter的this上下文自动地绑定为......
  • HTML基础学习
    1.HTML表单元素的使用<!doctypehtml><html><head><title>NEFU</title></head><body><center><h2><fontcolor="blue">中国百度</font></h2> <ahref="http://www.......
  • 关于第一次学习JavaScript程序调试心得
    源程序如上,源代码来源(刘永富博士-ExcelVBA编程开发下册)。运行之后,网页无反应,alert不弹窗。经查询https://www.runoob.com/jsref/event-body-onload.htmlhttps://blog.csdn.net/sinat_29398599/article/details/65450485需添加onload事件。Bodyonload事件,onload事件在页......
  • AUTOSAR笔记:AUTOSAR软件组件级设计与开发(三)
    目录Matlab/Simulink与EmbeddedCoder工具Matlab/Simulink工具简介EmbeddedCoder工具基于Matlab/Simulink软件组件开发Matlab/Simulink与AUTOSAR基本概念的对应关系软件组件内部行为建模方法AUTOSAR客户端/服务器机制的实现方法软件组件(SWC)代码及描述文件配置生成求解器及代码生......
  • Spring MVC官方文档学习笔记(二)之DispatcherServlet
    1.DispatcherServlet入门(1)SpringMVC是以前端控制器模式(即围绕着一个中央的Servelt,DispatcherServlet)进行设计的,这个DispatcherServlet为请求的处理提供了一个共用的算法,即它都会将实际的处理工作委托给那些可配置的组件进行执行,说白了,DispatcherServlet的作用就是统......
  • 学习日记——吃货联盟系统项目的实现
    0.目录1.需求分析2.初始化订单3.主页面框架搭建4.各模块功能实现1.需求分析需求:主页面实现用户在个功能之间的选择和返回,实现用户的分支选择判断查看餐袋用户可以查看目前订单详情签收订单用户可以选择预定状态的订单完成签收删除订单用户可以选择已签收的......
  • 学习文章:即时通信的安全加密通信模型研究
    学习文章:即时通信的安全加密通信模型研究,具体见原论文摘要重点:即时通信的安全性和易用性。主要工作:分析国内外即时通信的安全通道模型、详细讨论起消息加密和发送流程、给出不同加密模式下的群聊和多设备端的消息转发原理,设计端到端加密的安全通道模型,分析各种安全通信模型的......
  • 神经网络与深度学习
    神经网络与深度学习(邱锡鹏)第一部分机器学习基础第1章绪论深度学习是机器学习的一个分支,指从有限样例中通过算法总结出一般性的规律,并可以应用到新的未知数据上。一种可以比较好解决贡献度分配问题的模型是人工神经网络(ArtificialNeuralNetwork,ANN),也简称神经网络。贡献......