Xenon's Attack on the Gangs

题意翻译

在 A.R.C.Markland-N 的另一层 Simon "Xenon" Jackson 早完成了他的项目后，便一如既往地休息一下。 由于拥有大量的空闲时间，他决定发挥传奇的黑客"X"本能，与网络世界的帮派作斗争。 ------ 现在有一棵$n$个结点的树 每条边分别分配了一个$[0,n-2]$的整数权值$w$，所有分配的整数都是不同的，并且每个整数都分配给某条边。 定义 : $$S_{path(s,t)}=mex_{(u,v)\in path(s,t)}w(u,v)$$ 要求最大化 $$\sum_{1\leq s < t \leq n}S_{path(s,t)}$$ $mex$ : 即集合中没有出现的最小自然数

题目描述

[INSPION FullBand Master - INSPION](https://www.youtube.com/watch?v=kwsciXm_7sA) [INSPION - IOLITE-SUNSTONE](https://www.youtube.com/watch?v=kwsciXm_7sA) On another floor of the A.R.C. Markland-N, the young man Simon "Xenon" Jackson, takes a break after finishing his project early (as always). Having a lot of free time, he decides to put on his legendary hacker "X" instinct and fight against the gangs of the cyber world. His target is a network of $ n $ small gangs. This network contains exactly $ n - 1 $ direct links, each of them connecting two gangs together. The links are placed in such a way that every pair of gangs is connected through a sequence of direct links. By mining data, Xenon figured out that the gangs used a form of cross-encryption to avoid being busted: every link was assigned an integer from $ 0 $ to $ n - 2 $ such that all assigned integers are distinct and every integer was assigned to some link. If an intruder tries to access the encrypted data, they will have to surpass $ S $ password layers, with $ S $ being defined by the following formula: $ $S = \sum_{1 \leq u < v \leq n} mex(u, v) $ $ </p><p>Here, $ mex(u, v) $ denotes the smallest non-negative integer that does not appear on any link on the unique simple path from gang $ u $ to gang $ v $ .</p><p>Xenon doesn't know the way the integers are assigned, but it's not a problem. He decides to let his AI's instances try all the passwords on his behalf, but before that, he needs to know the maximum possible value of $ S $ , so that the AIs can be deployed efficiently.</p><p>Now, Xenon is out to write the AI scripts, and he is expected to finish them in two hours. Can you find the maximum possible $ S$ before he returns?

输入输出格式

输入格式

The first line contains an integer $ n $ ( $ 2 \leq n \leq 3000 $ ), the number of gangs in the network. Each of the next $ n - 1 $ lines contains integers $ u_i $ and $ v_i $ ( $ 1 \leq u_i, v_i \leq n $ ; $ u_i \neq v_i $ ), indicating there's a direct link between gangs $ u_i $ and $ v_i $ . It's guaranteed that links are placed in such a way that each pair of gangs will be connected by exactly one simple path.

输出格式

Print the maximum possible value of $ S $ — the number of password layers in the gangs' network.

输入输出样例

输入样例 #1

3
1 2
2 3

输出样例 #1

3

输入样例 #2

5
1 2
1 3
1 4
3 5

输出样例 #2

10

说明

In the first example, one can achieve the maximum $ S $ with the following assignment: With this assignment, $ mex(1, 2) = 0 $ , $ mex(1, 3) = 2 $ and $ mex(2, 3) = 1 $ . Therefore, $ S = 0 + 2 + 1 = 3 $ . In the second example, one can achieve the maximum $ S $ with the following assignment: With this assignment, all non-zero mex value are listed below: - $ mex(1, 3) = 1 $ - $ mex(1, 5) = 2 $ - $ mex(2, 3) = 1 $ - $ mex(2, 5) = 2 $ - $ mex(3, 4) = 1 $ - $ mex(4, 5) = 3 $ Therefore, $ S = 1 + 2 + 1 + 2 + 1 + 3 = 10 $ .

题意翻译

在 A.R.C.Markland-N 的另一层 Simon "Xenon" Jackson 早完成了他的项目后，便一如既往地休息一下。 由于拥有大量的空闲时间，他决定发挥传奇的黑客"X"本能，与网络世界的帮派作斗争。 ------ 现在有一棵$n$个结点的树 每条边分别分配了一个$[0,n-2]$的整数权值$w$，所有分配的整数都是不同的，并且每个整数都分配给某条边。 定义 : $$S_{path(s,t)}=mex_{(u,v)\in path(s,t)}w(u,v)$$ 要求最大化 $$\sum_{1\leq s < t \leq n}S_{path(s,t)}$$ $mex$ : 即集合中没有出现的最小自然数