热门标签 | HotTags
当前位置:  开发笔记 > 后端 > 正文

树上区间问题—树链剖分

本博客主要是对前辈们的内容我认为好的部分摘取过来了《入门》LCA用轻重链剖分解决:好博客:https:www.cnblogs.comivanovcraftp9019090.html

本博客主要是对前辈们的内容我认为好的部分摘取过来了


《入门》

LCA用轻重链剖分解决:

好博客:https://www.cnblogs.com/ivanovcraft/p/9019090.html

https://www.luogu.com.cn/blog/by-random/solution-p3379

 

 

 

 

 

 

 

#include
#include

#include

#include

using namespace std;
const int N = 500010;
vector
<int> tree[N];
int n, m, s;
//节点的父节点,重子儿子,深度,子树的大小
//规定:根节点dep=1,f=0; size包含自身;
int f[N], son[N], dep[N], size[N];
bool st[N];
//求出节点的f,son,dep,size
void dfs1(int s)
{
if (!st[s])
{
st[s]
= true;
size[s]
+= 1;
int maxv = 0, v = s;
for (int i = 0; i )
{
int child = tree[s][i];
if (!st[child])
{
dep[child]
= dep[s] + 1;
f[child]
= s;
dfs1(child);
size[s]
+= size[child];
if (size[child] > maxv)
{
maxv
= size[child];
v
= child;
}
}
}
son[s]
= v;
}
}
//规定:根节点top=自己,轻链top=自己
int top[N];
// dfs2将重链的链顶改变
void dfs2(int s)
{
if (!st[s])
{
st[s]
= true;
for (int i = 0; i )
{
int child = tree[s][i];
if (!st[child] && son[s] == child)
top[child]
= top[s];
dfs2(child);
}
}
}
int main()
{
scanf(
"%d%d%d", &n, &m, &s);
for (int i = 1; i <= n-1; i++)
{
int a, b;
scanf(
"%d%d", &a, &b);
tree[a].push_back(b), tree[b].push_back(a);
}
f[s]
= 0, dep[s] = 1;
dfs1(s);
memset(st,
false, sizeof(st));
for (int i = 1; i <= n; i++)
top[i]
= i;
dfs2(s);
while (m--)
{
int a, b;
scanf(
"%d%d", &a, &b);
while (top[a] != top[b])
{
//将a与b跳到同一条链上
//指定a是dep[top[a]]更大的
if (dep[top[a]] < dep[top[b]])
swap(a, b);
a
= f[top[a]];
}
int res = dep[a] a : b;
printf("%d\n", res);
}
return 0;
}

 



推荐阅读
  • 本文详细介绍如何在VSCode中配置自定义代码片段,使其具备与IDEA相似的代码生成快捷键功能。通过具体的Java和HTML代码片段示例,展示配置步骤及效果。 ... [详细]
  • 本文详细介绍了如何准备和安装 Eclipse 开发环境及其相关插件,包括 JDK、Tomcat、Struts 等组件的安装步骤及配置方法。 ... [详细]
  • 本文详细介绍了网络存储技术的基本概念、分类及应用场景。通过分析直连式存储(DAS)、网络附加存储(NAS)和存储区域网络(SAN)的特点,帮助读者理解不同存储方式的优势与局限性。 ... [详细]
  • 嵌入式开发环境搭建与文件传输指南
    本文详细介绍了如何为嵌入式应用开发搭建必要的软硬件环境,并提供了通过串口和网线两种方式将文件传输到开发板的具体步骤。适合Linux开发初学者参考。 ... [详细]
  • 在Windows Server 2008 R2上配置IIS FTP服务
    本文详细介绍了如何在Windows Server 2008 R2操作系统上通过IIS配置FTP服务的过程,包括服务器角色的选择与安装、FTP站点的创建以及必要的服务和防火墙设置检查。 ... [详细]
  • 在Linux系统上构建Web服务器的详细步骤
    本文详细介绍了如何在Linux系统上搭建Web服务器的过程,包括安装Apache、PHP和MySQL等关键组件,以及遇到的一些常见问题及其解决方案。 ... [详细]
  • QUIC协议:快速UDP互联网连接
    QUIC(Quick UDP Internet Connections)是谷歌开发的一种旨在提高网络性能和安全性的传输层协议。它基于UDP,并结合了TLS级别的安全性,提供了更高效、更可靠的互联网通信方式。 ... [详细]
  • 本文详细介绍了如何使用Python编写爬虫程序,从豆瓣电影Top250页面抓取电影信息。文章涵盖了从基础的网页请求到处理反爬虫机制,再到多页数据抓取的全过程,并提供了完整的代码示例。 ... [详细]
  • 本文介绍如何在现有网络中部署基于Linux系统的透明防火墙(网桥模式),以实现灵活的时间段控制、流量限制等功能。通过详细的步骤和配置说明,确保内部网络的安全性和稳定性。 ... [详细]
  • 本文介绍了一种适用于小型创业公司的小规模每日数据备份及健康检查的自动化解决方案。通过简单的Shell脚本实现本地数据库的每日全量备份,并将备份文件上传至中心备份服务器。同时,编写了自动检测脚本来确保备份的完整性和及时性,一旦发现异常,会通过邮件和短信通知相关人员。 ... [详细]
  • 本文详细介绍了如何下载并安装 Python,包括选择合适的版本、执行安装程序以及设置环境变量的步骤。此外,还提供了测试安装是否成功的简单方法。 ... [详细]
  • 本文详细介绍了 phpMyAdmin 的安装与配置方法,适用于多个版本的 phpMyAdmin。通过本教程,您将掌握从下载到部署的完整流程,并了解如何根据不同的环境进行必要的配置调整。 ... [详细]
  • 本文介绍如何配置SecureCRT以正确显示Linux终端的颜色,并解决中文显示问题。通过简单的步骤设置,可以显著提升使用体验。 ... [详细]
  • Google排名优化-面向Google(Search Engine Friendly)的URL设计 ... [详细]
  • CentOS 7.2 配置防火墙端口开放
    本文介绍如何在 CentOS 7.2 系统上配置防火墙以开放特定的服务端口,包括 FTP 服务的临时与永久开放方法,以及如何验证配置是否生效。 ... [详细]
author-avatar
火影魂XJ_710
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有