树型贪心orz
写丑了。调了半个晚上，然后发现是起点最耗时的时候的情况搞错了，只用走n-1条路而不是n条。晕。
对于每个节点贪心按f[p]-2*sz[p]排序或者用原式也行。不过巨慢。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
int _d_;
#define readInt(_x_) { \
int& _s_ = (_x_ = 0); \
while (!isdigit(_d_ = getchar())); \
while (_s_ = _s_ * 10 + _d_ - 48, isdigit(_d_ = getchar())); \
}
struct edge {
int t;
edge *next;
};
const int maxn = 500009;
int n, v[maxn], t, f[maxn], sz[maxn], dfo[maxn], st[maxn];
edge *ep, *head[maxn];
inline void addEdge(int u, int v) {
ep-> t = v;
ep-> next = head[u];
head[u] = ep ++;
}
inline bool cmpTo(const int& a, const int& b) {
return max(f[a], f[b] + sz[a] * 2 + 1) < max(f[b], f[a] + sz[b] * 2 + 1);
//return f[a] - sz[a] * 2 > f[b] - sz[b] * 2 || (f[a] - sz[a] * 2 == f[b] - sz[b] * 2 && f[a] > f[b]);
}
void dfs() {
static int stc[maxn];
int tst = 1, dfn = 0;
stc[1] = 1;
memset(f, -1, sizeof(f));
memset(sz, 0, sizeof(sz));
f[1] = 0;
while (tst) {
int p = stc[tst --];
dfo[++ dfn] = p;
for (edge* e = head[p]; e; e = e-> next)
if (f[e-> t] == -1) {
f[e-> t] = 0;
stc[++ tst] = e-> t;
}
}
for (int ti = n; ti; -- ti) {
int p = dfo[ti], wt = 0;
t = 0;
f[p] = v[p];
sz[p] = 1;
for (edge* e = head[p]; e; e = e-> next)
if (sz[e-> t]) {
sz[p] += sz[e-> t];
st[t ++] = e-> t;
}
sort(st, st + t, cmpTo);
for (int i = 0; i < t; ++ i) {
f[p] = max(f[p], wt + f[st[i]] + 1);
wt += sz[st[i]] << 1;
}
}
}
int main() {
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
#endif
readInt(n);
for (int i = 1; i <= n; ++ i)
readInt(v[i]);
ep = new edge[n << 1];
memset(head, 0, sizeof(head));
for (int i = 1; i < n; ++ i) {
int u, v;
readInt(u);
readInt(v);
addEdge(u, v);
addEdge(v, u);
}
int v1 = v[1];
v[1] = 0;
dfs();
printf("%d\n", max(f[1], (n - 1) * 2 + v1));
}