# Long Live the Queen

## 题目描述

The Queen of Byteland is very loved by her people. In order to show her their love, the Bytelanders have decided to conquer a new country which will be named according to the queen’s name. This new country contains $N$ towns. The towns are connected by bidirectional roads and there is exactly ONE path between any two towns, walking on the country’s roads. For each town, the profit it brings to the owner is known. Although the Bytelanders love their queen very much, they don’t want to conquer all the $N$ towns for her. They will be satisfied with a non-empty subset of these towns, with the following $2$ properties: there exists a path from every town in the subset to every other town in the subset walking only through towns in the subset and the profit of the subset is maximum. The profit of a subset of the $N$ towns is equal to the sum of the profits of the towns which belong to the subset. Your task is to find the maximum profit the Bytelanders may get.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

namespace std {
template <typename T> void maxify(T &a, T b) { b > a && (a = b); }
template <typename T> void minify(T &a, T b) { b < a && (a = b); }
}

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
static const int N = 16010;
int n, nume, h[N], w[N], f[2][N];
struct Edge {
int v, nxt;
} e[N << 1];
void add_edge(int u, int v) {
e[++ nume] = (Edge) { v, h[u] }, h[u] = nume;
e[++ nume] = (Edge) { u, h[v] }, h[v] = nume;
}
void input() {
io > n;
for (int i = 1; i <= n; ++ i) io > w[i];
for (int i = 1; i < n; ++ i) {
int u, v; io > u > v, add_edge(u, v);
}
}
void init() { memset(f, -0x3f, sizeof f); }
void dfs(int t, int fa) {
f[0][t] = w[t];
for (int i = h[t]; i; i = e[i].nxt)
if (e[i].v != fa) {
dfs(e[i].v, t);
maxify(f[1][t], max(f[0][e[i].v], f[1][e[i].v]));
f[0][t] += max(f[0][e[i].v], 0);
}
}
void process() { dfs(1, 0), io < max(f[0][1], f[1][1]) < '\n'; }

public:
void solve() { input(), init(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}

418 I'm a teapot