BZOJ1369 [Baltic2003] Gem

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#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;
}