这题直接贪心显然不可行.
考虑树形dp，用 \(f_i\) 表示到 \(i\) 人后，以 \(i\) 为根的所有人安装完的最短时间.
对于一个节点 \(u\), 假设拜访子节点的顺序为 \(v_1,v_2,...,v_m\) ，那么得到转移方程.
\[f_u = max(f_v + \sum\limits_{j = 1}^{i - 1}sum_j)
\]
其中 \(sum_i\) 表示拜访完以 \(i\) 为根的子树的所有人所花的时间,即 \((siz_i -1) *2\)
拜访的顺序考虑贪心
对于两个相邻整数 \(i,j\)? ,必须满足 \(f_j + \sum\limits_{k =1}^{j-1}sum_k<f_i+ \sum\limits_{k=1}^{i-1}sum_k+sum_j\)?
\(\to f_j+sum_i < f_i+sum_j\\\to f_j-sum_j<f_i-sum_i\)
所以只要将 \(f_i - sum_i\) 从大到小排序即可.
const int N = 5e5 + 10;
vector<int>e[N];
int f[N], a[N], g[N];
bool cmp(int x, int y) {return g[x] - f[x] > g[y] - f[y];}
void dfs(int u, int fa) {
for (int v : e[u]) {
if (v == fa)continue;
dfs(v, u);
}
sort(e[u].begin(), e[u].end(), cmp);
if (u != 1) g[u] = a[u];
for (int v : e[u]) {
if (v == fa)continue;
g[u] = max(g[u], g[v] + f[u] + 1);
f[u] += f[v] + 2;
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n; cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1, x, y; i < n; ++i) {
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);
}
dfs(1, 0);
cout << max(g[1], f[1] + a[1]);
}