# 树上设备的拆除顺序

预估时间限制：1.5 秒。内存限制：128 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

设备站即将关闭。各台设备停机前仍会产生收益或维护成本，管理者需要安排符合依赖关系的拆除顺序。

(本故事由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

### 输入

```text
5
-1 -1 -2 -2 -1
1 2
2 3
3 4
4 5
```

### 输出

```text
-13
5 4 3 2 1
```

### 样例 2

### 输入

```text
5
1 2 1 2 4
2 1
3 1
3 5
2 4
```

### 输出

```text
17
4 2 5 3 1
```

### 样例 3

### 输入

```text
5
0 0 0 0 0
1 2
2 5
1 3
3 4
```

### 输出

```text
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% | 无额外条件 |