首页 > 其他分享 >关于树的直径的一切

关于树的直径的一切

时间:2024-04-07 09:37:17浏览次数:19  
标签:一切 int Dfs fa 关于 ans 直径 dis

观前须知

本文使用 CC BY-NC-SA 4.0 许可
本文所有详细证明可见 OI Wiki

笔者的博客主页

正文

定义

树的直径指树上任意两点间距离的最大值

两次DFS

先以任意点为根找到最远点 \(v\)
再以 \(v\) 为根找到最远点 \(u\)
\(u-v\) 即为该树的一条直径

适用范围:无负权树
证明:
当 \(v\) 为直径的一个端点时显然成立
反证法假设存在更长路径
分类讨论+画图可得矛盾

代码:

int dis[AwA], ans;

void Dfs(int u, int fa) {
    if (dis[u] > dis[ans]) ans = u;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if (v == fa) continue;
        dis[v] = dis[u] + e[i].w;
        Dfs(v, u);
    }
}

int GetAns() {
    dis[1] = ans = 0;
    Dfs(1, 0);
    dis[ans] = 0;
    Dfs(ans, 0);
    return dis[ans];
}

树型DP

Dfs,以当前点为中间点,考虑最长链和次长链,并把最长链继续上传

代码:

int f[AwA], ans;

void Dfs(int u, int fa) {
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if (v == fa) continue;
        Dfs(v, u);
        ans = max(ans, f[u] + f[v] + e[i].w);
        f[u] = max(f[u], f[v] + e[i].w);
    }
}

性质

树的权非负时,树的直径中点重合
反证法易证

标签:一切,int,Dfs,fa,关于,ans,直径,dis
From: https://www.cnblogs.com/Sugar-Cube/p/18118402

相关文章

  • 关于pwn题的栈平衡中ret的作用
    以nssctf里的where_is_my_shell为例题目提供了一个system函数,和一个buf数组。数组的栈空间如图所示,这里不讨论怎么解题,只说明payload里的ret的作用。假设没有ret,栈溢出到ret的时候内容如下:第一个八字节:(图示位置)存储poprdi;ret;的地址它下面的八个字节存储要pop的参数。......
  • 关于 VScode, 点击文件右键或者在文件夹中没有 【 在vscode中打开选项】 解决办法
    关于VScode,点击文件右键或者在文件夹中没有【在vscode中打开选项】解决办法段子手-1682024-4-61、在任意位置创建一个文本文件。如:a.txt2、复制以下代码到a.txt文本文件中。(注:以;开头的,是备注信息,不需要做任何修改)WindowsRegistryEditorVersion......
  • 关于LayuiAdmin单页版 点击 生成新的 tab标签页
    挠头一小时,解决一秒钟直接上代码html<buttonclass="layui-btnlayuiadmin-btn-useradmin"id="openNewTabBtn">添加</button>js layui.use(['element','table','jquery'],function(){ var$=layui.$ var......
  • 关于学术论文的一些认识
    1.什么是核心期刊、SCI核心期刊通常是指在特定学科领域内具有一定学术影响力和水平的期刊,经过权威机构认定,并受到学术界和科研机构的认可和重视。这些期刊通常具有严格的审稿制度、高质量的论文和较高的引用率。SCI(ScienceCitationIndex)是科学引文索引,是由美国科学信息研究所......
  • 36. 关于 SAP ABAP OData 服务如何实现 Deep Insert 场景 - SAP 应用的标准行为
    有朋友在知乎上向我咨询:OData更新多表数据的时候,可以做多层级结构的entity吗?多层的时候etag怎么做?比如我要更新表1.2.3。分别是header级别以及子层级别以及子层的子层。调用元调用一次会把三层的数据都给我们。如果put不可以做,一般odata这种怎么做。请赐教。......
  • 关于三级树形分类的解释(谷粒商城)
    在学谷粒商城的时候,老师并没有给三级树形分类这块讲清楚,导致在拖拽这块很多人都有疑问,在仔细琢磨下,看了这篇文章,只要明白这两个点,那就能理解了。层级和深度的关系:第一级节点的层级是0,深度是3第二级节点的层级是1,深度是2第三级节点的层级是2,深度是1letdeep......
  • 【爬虫】debug篇-关于fake_useragent无法使用:Error occurred during loading data. Tr
    Erroroccurredduringloadingdata.Tryingtousecacheserverhttps://fake-useragent.herokuapp.com/browsers/0.1.11Traceback(mostrecentcalllast):File"D:\python\lib\site-packages\fake_useragent\utils.py",line154,inloadfori......
  • 关于MySQL数据库的几个简单的入门代码注释
    不是很全,是我刚开始学习数据库时记的笔记%FOUND判断游标有效性%ROWTYPE行数据类型%属性:=赋值符号1ISTABLEOF21、2类型一样ABS系统自带函数绝对值ALL()比所有都ANY()任意一个(some用法意思一样)AS命别名,连接ASC升序AVG()函数求平均数BEGIN执行部分BULKCOLLECT......
  • 关于AI训练数据侵权的碎碎念
    从ChatGPT开始对于AI使用的训练数据是否侵权就一直争论不休,经常能看到xx行业联合抵制的新闻。尽管我个人认为是“侵权”的,但也知道大概率这并不违反任何现行法律(可能违法的是爬取训练数据这个过程),等到相关法律出台的时候互联网上的优质数据大概都已经被收集完成了,所以除了感慨......
  • 关于 npm 包的版本管理规范和各项配置项的含义
    关于npm包的版本管理规范和各项配置项的含义npmixxx@next安装最新的版本,不管是稳定版还是内测版npmixxx@latest安装最新的版本,并且是稳定版相关链接https://juejin.cn/post/7122240572491825160https://juejin.cn/post/7027293182249402405......