P4338 [ZJOI2018] 历史

九条可怜是一个热爱阅读的女孩子。

这个世界有 n 个城市，这 n 个城市被恰好 $n-1$ 条双向道路联通，即任意两个城市都可以 互相到达。同时城市 1 坐落在世界的中心，占领了这个城市就称霸了这个世界。 在最开始，这 n 个城市都不在任何国家的控制之下，但是随着社会的发展，一些城市会崛 起形成国家并夺取世界的霸权。为了方便，我们标记第 i 个城市崛起产生的国家为第 i 个国家。 在第 i 个城市崛起的过程中，第 i 个国家会取得城市 i 到城市 1 路径上所有城市的控制权。 新的城市的崛起往往意味着战争与死亡，若第 i 个国家在崛起中，需要取得一个原本被国 家 $j(j ≠ i)$ 控制的城市的控制权，那么国家 i 就必须向国家 j 宣战并进行战争。 现在，可怜知道了，在历史上，第 i 个城市一共崛起了 $a_i$ 次。但是这些事件发生的相对顺 序已经无从考究了，唯一的信息是，在一个城市崛起称霸世界之前，新的城市是不会崛起的。 战争对人民来说是灾难性的。可怜定义一次崛起的灾难度为崛起的过程中会和多少不同的国家进行战争（和同一个国家进行多次战争只会被计入一次）。可怜想要知道，在所有可能的崛 起顺序中，灾难度之和最大是多少。 同时，在考古学家的努力下，越来越多的历史资料被发掘了出来，根据这些新的资料，可怜会对 $a_i$ 进行一些修正。具体来说，可怜会对 $a_i$ 进行一些操作，每次会将 $a_x$ 加上 w。她希望 在每次修改之后，都能计算得到最大的灾难度。 然而可怜对复杂的计算并不感兴趣，因此她想让你来帮她计算一下这些数值。 对题面的一些补充： - 同一个城市多次崛起形成的国家是同一个国家，这意味着同一个城市连续崛起两次是不会 和任何国家开战的：因为这些城市原来就在它的控制之下。 - 在历史的演变过程中，第 i 个国家可能会有一段时间没有任何城市的控制权。但是这并不 意味着第 i 个国家灭亡了，在城市 i 崛起的时候，第 i 个国家仍然会取得 1 到 i 路径上的城市的控制权。

无

无

在修正开始之前，如果按照所在城市 4, 1, 5, 3, 2 的顺序崛起，那么依次会和 0, 1, 2, 1, 2 个 国家进行战争。 这时一共会产生 6 对敌对关系。可以证明这是所有崛起顺序中的最大值。