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) {
[cnt] = pre[x];
nxt[pre[x] = cnt++] = y;
to[cnt] = pre[y];
nxt[pre[y] = cnt++] = x;
to}
struct Msg {
int m1, m1v, m2v;
() {}
Msgvoid upd(int x, int v) {
if (v < m1v) {
std::swap(x, m1);
std::swap(v, m1v);
}
if (v < m2v)
= v;
m2v }
} F[N];
int C[N];
bool vis[N];
void Solve(int x, int f) {
int S = 0;
&ans = F[x];
Msg .m1v = ans.m2v = INF;
ansfor (int i = pre[x]; ~i; i = nxt[i]) if (to[i] != f)
(to[i], x);
Solvefor (int i = pre[x]; ~i; i = nxt[i]) if (to[i] != f) {
&t = F[to[i]];
Msg += t.m1v;
S [t.m1] += t.m2v - t.m1v;
C[t.m1] = true;
vis}
int k = 1;
while (vis[k]) ++k;
.upd(k, S + k);
answhile (vis[++k]);
.upd(k, S + k);
ansfor (int i = pre[x]; ~i; i = nxt[i]) if (to[i] != f) {
&t = F[to[i]];
Msg if (!vis[t.m1]) continue;
.upd(t.m1, S + C[t.m1] + t.m1);
ans[t.m1] = false;
vis[t.m1] = 0;
C}
}
int main() {
= readInt();
n (pre, -1, sizeof pre);
memsetfor (int i = 1; i < n; ++i) addEdge(readInt(), readInt());
(1, 0);
Solve("%d\n", F[1].m1v);
printfreturn 0;
}