#PQJ36x2305. QOJ 36_2305
QOJ 36_2305
2 历史 2.1 题目描述 九条可怜是一个热爱阅读的女孩子。 这段时间,她看了一本非常有趣的小说,这本小说的架空世界引起了她的兴趣。 这个世界有n 个城市,这n 个城市被恰好n −1 条双向道路联通,即任意两个城市都可以 互相到达。同时城市1 坐落在世界的中心,占领了这个城市就称霸了这个世界。 在最开始,这n 个城市都不在任何国家的控制之下,但是随着社会的发展,一些城市会崛 起形成国家并夺取世界的霸权。为了方便,我们标记第i 个城市崛起产生的国家为第i 个国家。 在第i 个城市崛起的过程中,第i 个国家会取得城市i 到城市1 路径上所有城市的控制权。 新的城市的崛起往往意味着战争与死亡,若第i 个国家在崛起中,需要取得一个原本被国 家j(j̸ = i) 控制的城市的控制权,那么国家i 就必须向国家j 宣战并进行战争。 现在,可怜知道了,在历史上,第i 个城市一共崛起了ai 次。但是这些事件发生的相对顺 序已经无从考究了,唯一的信息是,在一个城市崛起称霸世界之前,新的城市是不会崛起的。 战争对人民来说是灾难性的。可怜定义一次崛起的灾难度为崛起的过程中会和多少不同的 国家进行战争(和同一个国家进行多次战争只会被计入一次)。可怜想要知道,在所有可能的崛 起顺序中,灾难度之和最大是多少。 同时,在考古学家的努力下,越来越多的历史资料被发掘了出来,根据这些新的资料,可 怜会对ai 进行一些修正。具体来说,可怜会对ai 进行一些操作,每次会将ax 加上w。她希望 在每次修改之后,都能计算得到最大的灾难度。 然而可怜对复杂的计算并不感兴趣,因此她想让你来帮她计算一下这些数值。 对题面的一些补充: • 同一个城市多次崛起形成的国家是同一个国家,这意味着同一个城市连续崛起两次是不会 和任何国家开战的:因为这些城市原来就在它的控制之下。 • 在历史的演变过程中,第i 个国家可能会有一段时间没有任何城市的控制权。但是这并不 意味着第i 个国家灭亡了,在城市i 崛起的时候,第i 个国家仍然会取得1 到i 路径上的 城市的控制权。 2.2 输入Ḑᓣ 第一行输入两个整数n, m 表示城市个数和操作个数。 第二行输入n 个整数表示ai 的初始值。 接下来n −1 行,每行输入两个整数ui, vi(1 ≤ui, vi ≤n) 描述了一条道路。 接下来m 行每行输入两个整数xi, wi 表示将axi 加上wi。 4
2.3 输出Ḑᓣ 输出共m + 1 行,第一行表示初始的ai 的答案,接下来m 行每行表示这次修正后的答案。 2.4 样例输入 5 3 1 1 1 1 1 1 2 1 3 2 4 2 5 2 1 3 1 4 1 2.5 样例输出 6 7 9 10 2.6 样例解䞞 在修正开始之前,如果按照所在城市4, 1, 5, 3, 2 的顺序崛起,那么依次会和0, 1, 2, 1, 2 个 国家进行战争。这时一共会产生6 对敌对关系。可以证明这是所有崛起顺序中的最大值。 2.7 数据㣗ೈ与约定 测试点 n m 其他约定 1 ≤10 = 0 ai = 1 2 ≤150000 ≤150000 第i 条道路连接i 和i + 1 3 4 = 0 无 5 6 ≤150000 7 8 9 ≤4 × 105 ≤4 × 105 10 对于100% 的数据,1 ≤ai, wi ≤107, 1 ≤xi ≤n 5