树上设备的拆除顺序¶
预估时间限制：1.5 秒。内存限制：128 MB。
实际时限以标准程序在目标环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
设备站即将关闭。各台设备停机前仍会产生收益或维护成本，管理者需要安排符合依赖关系的拆除顺序。
(本故事由GPT-6重写)
形式化问题描述¶
有一棵包含 \(n\) 个节点的树，以节点 \(1\) 为根。节点编号为 \(1,\ldots,n\) ，节点 \(i\) 的每小时生产值为整数 \(p_i\) ，可以为负。
从时刻零开始，每小时恰好拆除一个节点。只有在所有儿子均已拆除后，才能开始拆除该节点。拆除耗时一小时，开始拆除后不再生产。因此，第 \(k\) 个拆除的节点此前生产了 \(k-1\) 小时。若顺序为 \(v_1,\ldots,v_n\) ，总生产值为
\[
\sum_{k=1}^{n}(k-1)p_{v_k}.
\]
求最大总生产值，并在所有最优合法顺序中，输出字典序最小的节点编号序列。字典序在首个不同位置比较编号。
输入格式¶
第一行一个整数 \(n\) .第二行给出 \(p_1,\ldots,p_n\) .接下来 \(n-1\) 行，每行两个整数 \(u,v\) ，表示树的一条无向边；父子方向由根 \(1\) 确定。
输出格式¶
第一行输出最大总生产值。第二行输出字典序最小的最优拆除顺序，共 \(n\) 个整数。
样例¶
样例 1¶
输入¶
5
-1 -1 -2 -2 -1
1 2
2 3
3 4
4 5
输出¶
-13
5 4 3 2 1
样例 2¶
输入¶
5
1 2 1 2 4
2 1
3 1
3 5
2 4
输出¶
17
4 2 5 3 1
样例 3¶
输入¶
5
0 0 0 0 0
1 2
2 5
1 3
3 4
输出¶
0
4 3 5 2 1
样例解释¶
样例一的合法顺序唯一，其总生产值为 \(0(-1)+1(-2)+2(-2)+3(-1)+4(-1)=-13\) .样例二顺序 \(4,2,5,3,1\) 的值为 \(17\) .样例三所有合法顺序的生产值均为零，仍须满足字典序最小的要求。
数据范围与保证¶
\(1\le n\le500000\) ，\(|p_i|\le1000000\) .输入的边构成一棵树。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |