算法
(染色问题、构造、树上dfs) $O(N)$
容易发现,最少染色数等于给树上的度数最大的顶点所需的颜色
关于颜色的分配,若点 $v$ 对应的前一条边的颜色固定,不妨记为 $c$,对于 $v$ 与其孩子节点 $u$ 相连的边的染色,我们只需从 $1$ 开始枚举,若此时的颜色与 $c$ 相同则加一。
总结:除了最短路以外的问题尽量用 dfs
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::max;
using std::vector;
struct Edge {
int to, id;
Edge() {}
Edge(int to, int id): to(to), id(id) {}
};
int main() {
int n;
cin >> n;
vector<vector<Edge>> g(n);
rep(i, n - 1) {
int a, b;
cin >> a >> b;
--a; --b;
g[a].emplace_back(b, i);
g[b].emplace_back(a, i);
}
vector<int> ans(n);
auto dfs = [&](auto& f, int v, int c=-1, int p=-1) -> void {
int k = 1;
rep(i, g[v].size()) {
int u = g[v][i].to, ei = g[v][i].id;
if (u == p) continue;
if (k == c) ++k;
ans[ei] = k++;
f(f, u, ans[ei], v);
}
};
dfs(dfs, 0);
int mx = 0;
rep(i, n) mx = max(mx, int(g[i].size()));
cout << mx << '\n';
rep(i, n - 1) {
cout << ans[i] << '\n';
}
return 0;
}
// 实现2
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::max;
using std::vector;
using std::queue;
struct Edge {
int to, id;
Edge() {}
Edge(int to, int id): to(to), id(id) {}
};
int main() {
int n;
cin >> n;
vector<vector<Edge>> g(n);
rep(i, n - 1) {
int a, b;
cin >> a >> b;
--a; --b;
g[a].emplace_back(b, i);
g[b].emplace_back(a, i);
}
queue<int> q;
vector<int> used(n), ans(n);
q.push(0);
used[0] = 1;
while (q.size()) {
int v = q.front(); q.pop();
int c = -1;
rep(i, g[v].size()) {
int u = g[v][i].to, ei = g[v][i].id;
if (used[u]) c = ans[ei];
}
int k = 1;
rep(i, g[v].size()) {
int u = g[v][i].to, ei = g[v][i].id;
if (used[u]) continue;
if (k == c) ++k;
ans[ei] = k++;
q.push(u);
used[u] = 1;
}
}
int mx = 0;
rep(i, n) mx = max(mx, int(g[i].size()));
cout << mx << '\n';
rep(i, n - 1) {
cout << ans[i] << '\n';
}
return 0;
}
大佬的马蜂 真不错QAQ