BZOJ1369 [Baltic2003] Gem

2018 年 12 月 26 日发布.

Description

给出一棵 $n$ 个结点的树，要求给每个点一个正整数权值，使得相邻的结点的权值不相等，且最小化权值和。

$n\leqslant10^4$。

Solution

考虑令 $f_{i,j}$ 表示 $i$ 结点标成 $j$ 的时候其子树最小权值和。

$$f_{i,j}=\sum_k\min_{t\neq j}f_{k,t}$$

其中 $k$ 取遍 $i$ 的儿子。可以发现对每个 $i$，所有 $f_{i,j}$ 中只有最小值和次小值可能用得到。

所以记录最小值、最小值对应的 $j$ 和次小值即可。复杂度 $O(n)$。

Code

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

const int N = 10050;
const int INF = N * N;

int n, pre[N], nxt[N * 2], to[N * 2], cnt;

int readInt() {
  int ans = 0, c, f = 1;
  while (!isdigit(c = getchar()))
    if (c == '-') f = -1;
  do ans = ans * 10 + c - '0';
  while (isdigit(c = getchar()));
  return ans * f;
}

inline void addEdge(int x, int y) {
  nxt[cnt] = pre[x];
  to[pre[x] = cnt++] = y;
  nxt[cnt] = pre[y];
  to[pre[y] = cnt++] = x;
}

struct Msg {
  int m1, m1v, m2v;
  Msg() {}
  void upd(int x, int v) {
    if (v < m1v) {
      std::swap(x, m1);
      std::swap(v, m1v);
    }
    if (v < m2v)
      m2v = v;
  }
} F[N];

int C[N];
bool vis[N];

void Solve(int x, int f) {
  int S = 0;
  Msg &ans = F[x];
  ans.m1v = ans.m2v = INF;
  for (int i = pre[x]; ~i; i = nxt[i]) if (to[i] != f)
    Solve(to[i], x);
  for (int i = pre[x]; ~i; i = nxt[i]) if (to[i] != f) {
    Msg &t = F[to[i]];
    S += t.m1v;
    C[t.m1] += t.m2v - t.m1v;
    vis[t.m1] = true;
  }
  int k = 1;
  while (vis[k]) ++k;
  ans.upd(k, S + k);
  while (vis[++k]);
  ans.upd(k, S + k);
  for (int i = pre[x]; ~i; i = nxt[i]) if (to[i] != f) {
    Msg &t = F[to[i]];
    if (!vis[t.m1]) continue;
    ans.upd(t.m1, S + C[t.m1] + t.m1);
    vis[t.m1] = false;
    C[t.m1] = 0;
  }
}

int main() {
  n = readInt();
  memset(pre, -1, sizeof pre);
  for (int i = 1; i < n; ++i) addEdge(readInt(), readInt());
  Solve(1, 0);
  printf("%d\n", F[1].m1v);
  return 0;
}