# 多棵树中的共同连通集

预估时间限制：3 秒。内存限制：512 MB。

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

## 背景故事

观测站需要同时适应几种通信布局。选出的观测站在每种布局中都应保持连通，规划员希望使它们的总收益最大。

(本故事由GPT-6重写)

## 形式化问题描述

有 $n$ 个点，编号为 $1,\ldots,n$ ，点 $i$ 的整数权值为 $a_i$ ，可以为负。给出 $m$ 棵使用同一组点的树。

选择点集 $S$ ，使它在每棵树中的诱导子图都连通：连接任意两选中点的唯一路径也只能经过选中点。允许 $S$ 为空，此时视为可行且权值和为零。

求最大权值和 $\sum_{i\in S}a_i$ .

## 输入格式

第一行两个整数 $n,m$ .第二行给出 $a_1,\ldots,a_n$ .接下来 $m$ 段，每段 $n-1$ 行；每行两个整数 $u,v$ ，表示对应树的一条无向边。

## 输出格式

输出一行一个整数，表示最大权值和。

## 样例

### 样例 1

### 输入

```text
3 1
-6 3 4
1 2
1 3
```

### 输出

```text
4
```

### 样例 2

### 输入

```text
7 2
-10 -3 3 5 7 2 1
1 2
1 3
2 4
2 5
3 6
3 7
1 2
1 7
2 4
2 5
7 6
7 3
```

### 输出

```text
9
```

### 样例 3

### 输入

```text
2 2
-2 -7
1 2
2 1
```

### 输出

```text
0
```

## 样例解释

样例一选择单点 $3$ 得到 $4$ ；同时选择 $2,3$ 必须加入 $1$ ，总和只有 $1$ .样例二选 $\{2,4,5\}$ ，在两棵树中都连通，收益为 $-3+5+7=9$ .样例三选空集。

## 数据范围与保证

$1\le n\le20000$ ，$1\le m\le5$ ，$|a_i|\le10^9$ .端点在 $1,\ldots,n$ 内；每段边构成一棵树。

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |