CF14D.Two Paths
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:64MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
As you know, Bob's brother lives in Flatland. In Flatland there are n cities, connected by n - 1 two-way roads. The cities are numbered from 1 to n. You can get from one city to another moving along the roads.
The «Two Paths» company, where Bob's brother works, has won a tender to repair two paths in Flatland. A path is a sequence of different cities, connected sequentially by roads. The company is allowed to choose by itself the paths to repair. The only condition they have to meet is that the two paths shouldn't cross (i.e. shouldn't have common cities).
It is known that the profit, the «Two Paths» company will get, equals the product of the lengths of the two paths. Let's consider the length of each road equals 1, and the length of a path equals the amount of roads in it. Find the maximum possible profit for the company.
众所周知,Bob 的兄弟住在平面国(Flatland)。平面国有 $ n $ 座城市,由 $ n-1 $ 条双向道路连接。城市编号为 $ 1 $ 到 $ n $,且任意两座城市之间均可通过道路相互到达。
Bob 的兄弟所就职的「两条路径」(Two Paths)公司中标,负责修复平面国中的两条路径。一条路径是指一系列互不相同的城市,这些城市按顺序由道路依次连接而成。该公司可自行选择待修复的两条路径,唯一要求是:这两条路径不能相交(即不能包含任何共同的城市)。
已知,「两条路径」公司所获利润等于这两条路径长度的乘积。我们规定每条道路的长度为 $ 1 $,而一条路径的长度定义为该路径所包含的道路数量。请计算该公司能获得的最大可能利润。
输入格式
The first line contains an integer n (2 ≤ n ≤ 200), where n is the amount of cities in the country. The following n - 1 lines contain the information about the roads. Each line contains a pair of numbers of the cities, connected by the road a__i, b__i (1 ≤ a__i, b__i ≤ n).
第一行包含一个整数 n(2≤n≤200),其中 n 表示该国的城市数量。接下来的 n−1 行描述了道路信息。每行包含一对由道路相连的城市编号 ai,bi(1≤ai,bi≤n)。
输出格式
Output the maximum possible profit.
输出可能获得的最大利润。
输入输出样例
输入#1
4 1 2 2 3 3 4
输出#1
1
输入#2
7 1 2 1 3 1 4 1 5 1 6 1 7
输出#2
0
输入#3
6 1 2 2 3 2 4 5 4 6 4
输出#3
4
输入解题思路,AI测评打分。不知道怎么写?