1025. 树的直径 - 数据结构与算法专题题库 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 512 MB

给定一个有 $n$ 的节点的树，计算树上最远的两个点之间的距离。

如果你已经知道该怎么做了，可以直接跳下面的部分。

首先，给定的是一棵无根树，无根树一般用边来表示。对于输入的树上的边建立类似双向图的存储结构。

随机选择一个节点，假设是 $1$ ，在以 $1$ 为根的有根树上进行一遍dfs或者bfs遍历，并记录下每个点到根 $1$ 的距离。

选择到根 $1$ 距离最远的点 $u$ （如果有多个，随机选择一个都可以），根据节点 $u$ 再建立一个有根树，这个时候以 $u$ 为根的有根树上进行一遍dfs或者bfs遍历，并记录下每个点到根 $u$ 的距离。

第二次遍历之后，距离 $u$ 最远的点对应的距离就是树的直径。

输入格式

一个行一个数 $n$ 表示树上节点的个数，满足 $n \leq 10^{6}$ 。

接下来 $n - 1$ 行，每行 $2$ 个数 $u, v$ ，表示 $u$ 和 $v$ 相连。

输入保证是一棵树。

输出格式

一个数，表示树的直径。

样例

Input

3
1 2
1 3

Output

提示

除了dfs的做法，还可以使用树形dp的做法。

1001. 栈的实现 1002. 铁路调度 1003. 数据生成器 1004. 队列的实现 1005. 座位分配 1006. 车厢调度 1007. Max Element 1008. 最小的n个和 1009. 数据整理 1010. 约瑟夫环问题 1011. 链表去重 1012. n皇后问题 1013. 迷宫搜索 1014. 构造字典序最小字符串 1015. 任务调度 1016. 快速排序 1017. 逆序对 1018. 最大最小问题 1019. 层次遍历 1020. 医疗队列 1021. 数独问题 1022. 终极背包问题 1023. 终极混合背包问题 1024. 分割回文串 1025. 树的直径 1026. 路径差 1027. 旅行商问题 1028. 数的变换 1029. 单峰序列 1030. 高级并查集 1031. 传送门（一） 1032. 传送门（三） 1033. 一元多项式乘法 1034. 表达式 1035. 恢复古诗 1036. 代码查重 1037. Take a party 1038. 小强的烦恼 1039. 树的双亲存储法 1040. A Knight's Journey 1041. 华师大卫星照片 1042. Can you do DFS? 1043. 斐波那契数列和 1044. 说出来可能不信这是排序题 1045. 最大的子串 1046. 最小等待时间 1047. 判断两个数是否相等 1048. 电话送报 1049. 简单排序题 1050. Ants 1051. 付款问题 1052. 数塔 1053. 最长连续公共子序列 1054. 整数的拆分 1055. 完全加括号的矩阵连乘积 1056. 装箱问题 1057. 统计字符串个数 1058. 子集和问题 1059. 区间覆盖 1060. 0-1背包问题 1061. 放书 1062. 经典的猜数游戏 1063. 最近点对 1064. 双人旋转赛车 1065. Hanoi Tower II 1066. Hanoi Tower III 1067. Hanoi Tower IV 1068. 奇异收缩的剪影