首页 > 试题广场 >

树上三角链

[编程题]树上三角链

给定一棵包含 $n$ $(n\geq3)$ 个节点且以节点 $1$ 为根节点的树。

你需要从中选出 $3$ 个不同的节点，使得其两两之间的最短距离之和最大，并求出这个最大和。

定义树上两点之间的最短距离为这两点之间的简单路径所经过的边的数量。

第一行输入一个正整数。
第二行输入个正整数。节点为节点的父节点。

输出一个整数代表最大和。

示例1

输入

5
4 1 1 4


3个节点为3，2，5
节点3与2的最短距离为3
节点3与5的最短距离为3
节点2与5的最短距离为2
3+3+2=8

算法知识视频讲解

暂无题解

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师安全工程师游戏研发工程师 2021 数据库工程师信息技术岗区块链测试开发工程师腾讯音乐娱乐集团大数据开发工程师数据分析师 Java工程师

上传者：小小

难度：

2条回答 19收藏 2805浏览

扫一扫，把题目装进口袋