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.

题意概述

给定一棵$N$个节点的树，每个节点都有权值。求它连通子图节点权值之和的最大值。

数据范围：$1 \le N \le 16000$。

算法分析

考虑树形 DP。假定$1$号点为根节点。令$f_{0, i}$表示$i$的子树中以$i$为根的连通子图节点权值之和的最大值，$f_{1, i}$表示$i$的子树中不以$i$为根的连通子图节点权值之和的最大值。

代码

#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;
}