关于树的直径的一切-Toy模板网

这篇具有很好参考价值的文章主要介绍了关于树的直径的一切。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

观前须知

笔者的博客主页

声明

本文使用 CC BY-NC-SA 4.0 许可。

本文为笔者在 OI 学习中的复习向学习笔记。
部分内容会比较简略。
如有好的习题会不断补充。

知识简介

以下部分详细证明可见 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] = 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);
    }
}

性质

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

习题

YbtOj P1577 数字转换

考虑到变为比自己小的因数和是有唯一性的，
那么可建树，以比自己小的因数和为父节点。
因数和比自己大的和 1 无父节点，则设为根。
那么问题变为在森林上求树的直径的最大值。
对每棵树分别求一遍即可。文章来源地址https://www.toymoban.com/news/detail-844406.html

到了这里，关于关于树的直径的一切的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！