当前位置: 首页 > news >正文

【树】树的直径和重心

目录

一.树的直径

(1)定义

(2)思路

(3)例题 

(4)std(第一小问)

二.树的重心

(1)介绍

(2)求重心

(3)例题

(4)AC


一.树的直径

(1)定义

树的直径是指树中最长的一条路径的长度,这条路径连接树中的两个节点,使得它们之间的距离最远。

(2)思路

(3)例题 

P3304 [SDOI2013] 直径 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

(4)std(第一小问)

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n;
struct Edge{int u,v,w,next;
}edge[maxn<<1];
int head[maxn],cnt;
void add(int u,int v,int w){edge[++cnt]=(Edge){u,v,w,head[u]}; head[u]=cnt;
}
int root,lon;
void dfs(int u,int fa,int p){if(p>lon){root=u;lon=p;}for(int i=head[u];i;i=edge[i].next){int v=edge[i].v;if(v==fa) continue;dfs(v,u,p+edge[i].w);}
}
int main(){scanf("%d",&n);for(int i=1,u,v,w;i<n;i++){scanf("%d%d%d",&u,&v,&w);add(u,v,w); add(v,u,w);}dfs(1,0,0);lon=0;dfs(root,0,0);printf("%d",lon);return 0;
}

二.树的重心

(1)介绍

 树的重心是指树中的一个节点,通过删除该节点后,将树分成多个子树,使得每个子树的节点数都不超过整棵树节点数的一半。换句话说,树的重心是树的一种结构特征,它能够将树尽可能平衡地分割成多个相对均匀的部分。

说人话就是重心在树所有节点中,它的最大子树的节点最小

寻找树的重心通常可以通过以下步骤来实现:

  1. 选择任意一个节点作为树的根节点。
  2. 对树进行深度优先搜索(DFS)或广度优先搜索(BFS),计算每个节点的子树大小(包括自身节点)。
  3. 对于每个节点,计算删除该节点后,各个子树的大小(即除去该节点后,以其邻居节点为根的子树大小)。
  4. 找到一个节点,使得删除该节点后,各个子树的大小都不超过整棵树节点数的一半。这个节点就是树的重心。

(2)求重心

#include<bits/stdc++.h>
#define maxn 10005
using namespace std;
int n;
int size[maxn],f[maxn]; //子树总大小 && 最大子树 
struct Edge{int u,v,next;
}edge[maxn<<1];
int head[maxn],cnt;
void add(int u,int v){edge[++cnt]=(Edge){u,v,head[u]}; head[u]=cnt;
}
int root,MAX=0x7fffffff;
void dfs(int u,int fa){size[u]=1;for(int i=head[u];i;i=edge[i].next){int v=edge[i].v;if(v!=fa){dfs(v,u);size[u]+=size[v];f[u]=max(f[u],size[v]);}}f[u]=max(f[u],n-size[u]);if(f[u]<MAX ||f[u]<=MAX && u<root){MAX=f[u];root=u;} 
}int main(){scanf("%d",&n);int x,y;for(int i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y); add(y,x);}dfs(1,0);printf("%d",root);return 0;
}

(3)例题

P1395 会议 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

(4)AC

#include<bits/stdc++.h>
#define maxn 50005
using namespace std;
int n;
int size[maxn],f[maxn]; //子树总大小 && 最大子树 
struct Edge{int u,v,w,next;
}edge[maxn<<1];
int head[maxn],cnt;
void add(int u,int v,int w){edge[++cnt]=(Edge){u,v,w,head[u]}; head[u]=cnt;
}
int root,MAX=0x7fffffff;
void dfs(int u,int fa){size[u]=1;for(int i=head[u];i;i=edge[i].next){int v=edge[i].v;if(v!=fa){dfs(v,u);size[u]+=size[v];f[u]=max(f[u],size[v]);}}f[u]=max(f[u],n-size[u]);if(f[u]<MAX ||f[u]<=MAX && u<root){MAX=f[u];root=u;} 
}
struct node{int u,w;bool operator < (const node &x) const{return x.w<w;}
};
int dis[maxn],vis[maxn];
void Djkstra(){for(int i=1;i<=n;i++) dis[i]=0x7fffffff;dis[root]=0;priority_queue<node> q;q.push((node){root,0});while(!q.empty()){node temp=q.top(); q.pop();int u=temp.u;if(vis[u]) continue;vis[u]=1;for(int i=head[u];i;i=edge[i].next){int v=edge[i].v,w=edge[i].w;if(dis[u]+w<dis[v]){dis[v]=dis[u]+w;q.push((node){v,dis[v]});}}}
}
int main(){scanf("%d",&n);int x,y;for(int i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y,1); add(y,x,1);}dfs(1,0);printf("%d ",root);Djkstra();long long ans=0;for(int i=1;i<=n;i++) ans+=dis[i];printf("%lld",ans);return 0;
}

相关文章:

【树】树的直径和重心

目录 一.树的直径 &#xff08;1&#xff09;定义 &#xff08;2&#xff09;思路 &#xff08;3&#xff09;例题 &#xff08;4&#xff09;std(第一小问) 二.树的重心 &#xff08;1&#xff09;介绍 &#xff08;2&#xff09;求重心 &#xff08;3&#xff09;例…...

《Attention Is All You Need》论文笔记

下面是对《Attention Is All You Need》这篇论文的浅读。 参考文献&#xff1a; 李沐论文带读 HarvardNLP 《哈工大基于预训练模型的方法》 下面是对这篇论文的初步概览&#xff1a; 对Seq2Seq模型、Transformer的概括&#xff1a; 下面是蒟蒻在阅读完这篇论文后做的一…...

C++笔记之不同buffer数量下的生产者-消费者机制

C笔记之不同buffer数量下的生产者-消费者机制 文章目录 C笔记之不同buffer数量下的生产者-消费者机制0.在不同的缓冲区数量下&#xff0c;生产者-消费者机制的实现方式和行为的区别1.最简单的生产者-消费者实现&#xff1a;抄自 https://mp.weixin.qq.com/s/G1lHNcbYU1lUlfugXn…...

编码文字使用整数xyz 三个坐标 并使用

导航 说明原始描述AI理解的实现代码说明 原始描述 而后期的,相同的s,前缀差距 和 自身权重 要对应的上,或者说 假设每个序列都是三维空间上的点集合,使用最小的空间表达这些信息,整个数据集才是重点。这些点的集合可以 是空间直线或者是曲线 整体的思路是 一个集合能在任…...

创建vue3工程

一、新建工程目录E:\vue\projectCode\npm-demo用Visual Studio Code 打开目录 二、点击新建文件夹按钮&#xff0c;新建vue3-01-core文件夹 三、右键vue3-01-core文件夹点击在集成终端中打开 四、初始化项目&#xff0c;输入npm init 一直敲回车直到创建成功如下图 npm init 五…...

Flutter笔记 - 用于描述Align的Alignment、AlignmentDirectional、AlignmentTween类

Flutter笔记 用于描述Align的Alignment、AlignmentDirectional、AlignmentTween类 作者&#xff1a;李俊才 &#xff08;jcLee95&#xff09;&#xff1a;https://blog.csdn.net/qq_28550263 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://blog.csdn.net/qq_…...

门面模式简介

门面模式简介 门面模式&#xff08;Facade Pattern&#xff09;是一种结构性设计模式&#xff0c;它提供了一个简化复杂系统的接口&#xff0c;允许客户端通过一个统一的接口与系统交互&#xff0c;而不需要了解系统内部的复杂性。这个模式的目标是降低客户端与系统之间的耦合…...

2023年7月工作经历二

invoke的翻译 C#的这个关键字很熟&#xff0c;但不知道如何翻译比较好。和网友沟通&#xff0c;并查阅多篇博文&#xff0c;觉得“同步调用&#xff08;invoke&#xff09;和异步调用(beginvoke)”比较好。 VS2022很爽 C#的类名&#xff0c;会提示命名空间。C调试的时候&…...

7.wifi开发【智能家居:终】,实践总结:智能开关,智能采集温湿,智能灯。项目运行步骤与运行细节,技术归纳与提炼,项目扩展

一。项目运行步骤与运行细节 1.项目运行步骤&#xff08;一定有其他的运行方式&#xff0c;我这里只提供一种我现在使用的编译方式&#xff09; &#xff08;1&#xff09;项目运行使用软件与技术&#xff1a; 1.Virtual linux 使用这个虚拟机进行程序的编译 2.Makefile与shl…...

学习开发一个RISC-V上的操作系统(汪辰老师) — unrecognized opcode `csrr t0,mhartid‘报错问题

前言 &#xff08;1&#xff09;此系列文章是跟着汪辰老师的RISC-V课程所记录的学习笔记。 &#xff08;2&#xff09;该课程相关代码gitee链接&#xff1b; &#xff08;3&#xff09;PLCT实验室实习生长期招聘&#xff1a;招聘信息链接 正文 &#xff08;1&#xff09;在跟着…...

【计算机网络】 心跳机制

文章目录 心跳机制应用场景什么是心跳机制心跳包的发送&#xff0c;通常有两种技术 心跳机制 应用场景 在长连接下&#xff0c;有可能很长一段时间没有数据往来。理论上说&#xff0c;这个连接是一直保持连接的&#xff0c;但是实际情况中&#xff0c;如果中间节点出现什么故…...

文心一言 VS 讯飞星火 VS chatgpt (106)-- 算法导论10.1 4题

四、用go语言&#xff0c;重写 ENQUEUE 和 DEQUEUE 的代码&#xff0c;使之能处理队列的下溢和上溢。 文心一言&#xff1a; 在 Go 语言中&#xff0c;我们可以使用切片来实现队列。下面是如何实现 ENQUEUE 和 DEQUEUE 操作&#xff0c;同时处理队列的下溢和上溢的情况&#…...

进程调度算法之时间片轮转调度(RR),优先级调度以及多级反馈队列调度

1.时间片轮转调度算法(RR) round Robin 1.算法思想 公平地、轮流地为各个进程服务&#xff0c;让每个进程在一定时间间隔内都可以得到响应。 2.算法规则 按照各进程到达就绪队列的顺序&#xff0c;轮流让各个进程执行一个时间片&#xff08;如100ms&#xff09;。 若进程未…...

ARMv8如何读取cache line中MESI 状态以及Tag信息(tag RAM dirty RAM)并以Cortex-A55示例

Cortex-A55 MESI 状态获取 一&#xff0c;系统寄存器以及读写指令二&#xff0c;Cortex-A55 Data cache的MESI信息获取&#xff08;AARCH 64&#xff09;2.1 将Set/way信息写入Data Cache Tag Read Operation Register2.2 读取Data Register 1和Data Register 0数据并解码 参考…...

密码技术 (6) - 证书

一. 前言 前面介绍的公钥密码和数字签名&#xff0c;都无法解决一个问题&#xff0c;那就是判断自己获取的公钥是否期望的&#xff0c;不能确定公钥是否被中间攻击人掉包。所以&#xff0c;证书的作用是用来证明公钥是否合法的。本文介绍的证书就是解决证书的可靠性的技术。 二…...

【算法学习】-【双指针】-【盛水最多的容器】

LeetCode原题链接&#xff1a;盛水最多的容器 下面是题目描述&#xff1a; 给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线&#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。…...

JAVA面经整理(8)

一)为什么要有区&#xff0c;段&#xff0c;页&#xff1f; 1)页是内存和磁盘之间交互的基本单位内存中的值修改之后刷到磁盘的时候还是以页为单位的索引结构给程序员提供了高效的索引实现方式&#xff0c;不过索引信息以及数据记录都是记录在文件上面的&#xff0c;确切来说是…...

【Java 进阶篇】JDBC数据库连接池Druid详解

在Java应用程序中&#xff0c;与数据库进行交互是一个常见的任务。为了更有效地管理数据库连接并提高性能&#xff0c;数据库连接池是一种常见的解决方案。Druid是一个流行的JDBC数据库连接池&#xff0c;它具有丰富的功能和高性能。本博客将详细介绍Druid连接池&#xff0c;包…...

Linux——指令初识

Linux下基本指令 前言一、 ls 指令二、 pwd命令三、cd 指令四、 touch指令五、mkdir指令六、rmdir指令 && rm 指令七、man指令八、cp指令九、mv指令十、cat指令十一、.more指令十二、less指令十三、head指令十四、tail指令总结 前言 linux的学习开始啦&#xff01; 今…...

专题一:双指针【优选算法】

双指针应用场景&#xff1a; 数组划分、数组分块 目录 一、移动0 二、复写0 从后向前 三、快乐数 链表带环 四、盛水最多的容器 单调性双指针 五、有效三角形个数 单调性双指针 六、和为s的两个数字 七、三数之和 细节多 需再练 一、移动0 class Solution { public:void move…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...