laekov

树型贪心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));

}