树的直径

约定不等于承诺〃 2022-05-12 11:04 171阅读 0赞

# 树的直径 #

树上最长的简单路径即为树的直径。

求树的直径的方法就是在树上任选一点u，求距离点u最远的点v，再求距离点v最远的点s，点u到点s的距离即为树的直径。（即两遍DFS或BFS求最远点）

证明：

1.  如果u 是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾)  
    2) 如果u不是直径上的点，则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了  
    所以v一定是直径的一个端点，所以从v进行BFS得到的一定是直径长度。

#include<cstdio>
    #include<cstring>
    #define N 4200
    struct hehe{ 
        int next;
        int to;
    }edge[N];
    int num_edge,head[N],dis[N],n,a,b,y;
    int add_edge(int from,int to){ 
        edge[++num_edge].next=head[from];
        edge[num_edge].to=to;
        head[from]=num_edge;
    }
    int dfs(int x){ 
        for(int i=head[x];i;i=edge[i].next)
            if(!dis[edge[i].to]){ 
                dis[edge[i].to]=dis[x]+1;
                dfs(edge[i].to);
            }
    }
    int main(){ 
        scanf("%d",&n);
        for(int i=1;i<n;++i){ 
            scanf("%d%d",&a,&b);
            add_edge(a,b);
            add_edge(b,a);
        }
        dfs(1);
        for(int i=y=1;i<=n;i++)
            if(dis[i]>dis[y])
                y=i;
        memset(dis,0,sizeof(dis));
        dfs(y);
        for(int i=y=1;i<=n;i++)
            if(dis[i]>dis[y])
                y=i;
        printf("%d",dis[y]);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，171人围观）

还没有评论，来说两句吧...

相关阅读

相关树的直径

树的直径 * 前言 * 源代码 * 参考博客前言路径：一棵树上，任意两个节点之间最多有一条简单路径。我们用 dis(a,b)表示点a和...

- 日理万妓/ 2024年04月17日 18:24/ 0 赞/ 64 阅读

相关【树的直径】树上子链

[F-树上子链\_牛客竞赛动态规划专题班树型dp例题 (nowcoder.com)][F-_dp_ _nowcoder.com] 题意： ![39c6a6eb334648c

秒速五厘米/ 2024年03月22日 17:39/ 0 赞/ 69 阅读

相关 543. 二叉树的直径

题目来源 [543. 二叉树的直径][543.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_sha

╰半夏微凉°/ 2022年12月19日 11:39/ 0 赞/ 156 阅读

相关树的直径（C++牛客网）

解题思路：（1）dfs class Solution { private: int max_sum=0; int end=

快来打我*/ 2022年11月18日 13:55/ 0 赞/ 136 阅读

相关 Leetcode 543. 二叉树的直径(直径 = 左子树高度 + 右子树高度)

题目重述给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。示例 : 给定二叉树

我不是女神ヾ/ 2022年09月02日 11:38/ 0 赞/ 180 阅读

相关 leetcode543二叉树的直径

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

傷城~/ 2022年08月29日 10:58/ 0 赞/ 168 阅读

相关树的直径（最远距离）

输入数据 5 5 1 2 2 2 4 3 2 5 1 4 5 4 1 3 5 有5个点5条边 ![Center][] 第一次bfs从1号

拼搏现实的明天。/ 2022年06月15日 04:30/ 0 赞/ 193 阅读

相关 [Leetcode][python]二叉树的直径

题目大意 [https://leetcode-cn.com/problems/diameter-of-binary-tree/description/][https_le

悠悠/ 2022年05月16日 06:29/ 0 赞/ 170 阅读

相关树的直径

树的直径树上最长的简单路径即为树的直径。求树的直径的方法就是在树上任选一点u，求距离点u最远的点v，再求距离点v最远的点s，点u到点s的距离即为树的直径。（即两遍D

约定不等于承诺〃/ 2022年05月12日 11:04/ 0 赞/ 172 阅读

相关 SDOI2013 直径（树的直径必经边）

SDOI2013 直径 [题目传送][Link 1] sol: 先求出任一直径同时把直径拎出来，树的非直径部分全部挂在直径上（如下）。 ![a][] 对于直径上的

- 日理万妓/ 2021年11月23日 23:12/ 0 赞/ 296 阅读