多棵树中的共同连通集¶
预估时间限制：3 秒。内存限制：512 MB。
实际时限以标准程序在目标环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
观测站需要同时适应几种通信布局。选出的观测站在每种布局中都应保持连通，规划员希望使它们的总收益最大。
(本故事由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¶
输入¶
3 1
-6 3 4
1 2
1 3
输出¶
4
样例 2¶
输入¶
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
输出¶
9
样例 3¶
输入¶
2 2
-2 -7
1 2
2 1
输出¶
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% | 无额外条件 |