当前位置: 首页 > 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…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

Vue 3 + WebSocket 实战:公司通知实时推送功能详解

&#x1f4e2; Vue 3 WebSocket 实战&#xff1a;公司通知实时推送功能详解 &#x1f4cc; 收藏 点赞 关注&#xff0c;项目中要用到推送功能时就不怕找不到了&#xff01; 实时通知是企业系统中常见的功能&#xff0c;比如&#xff1a;管理员发布通知后&#xff0c;所有用户…...