官方题解

题目大意

给定一棵有 $n$ 个点的树，需要给每条边染色，颜色编号为 $1\sim k$。要求对于任意一个点，与它相连的所有边颜色必须两两不同。判断是否存在合法方案，若存在输出任意一种。

题解思路

树的边染色要求“每个点相邻边颜色两两不同”，这就是树上的proper edge coloring。设树的最大度数为 $\Delta$。必要条件是 $k\ge \Delta$：因为度为 $\Delta$ 的点周围 $\Delta$ 条边必须用不同颜色。

对树而言这也是充分条件：当 $k\ge\Delta$ 时一定能染色。构造方法用一次 DFS 从根向下分配颜色即可。

把树以 1 为根。对每个点 $u$，设与父边的颜色为 parColor[u]（根为 0）。我们给 $u$ 的所有子边依次分配颜色 1..k，但跳过 parColor[u]，并且同一节点内部不重复。因为 $u$ 的子边数是 deg(u)-1（根是 deg(u)），而 $deg(u)\le k$，所以总能分配完且不会用到第 $k+1$ 种颜色。

实现上先用栈/队列求出父子关系，再按父到子的顺序给边赋色，复杂度 $O(n)$。

若 $k<\Delta$，直接输出 NO。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<int> eu(n), ev(n);
    vector<vector<pair<int,int>>> g(n + 1);
    vector<int> deg(n + 1, 0);

    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        eu[i] = u;
        ev[i] = v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
        deg[u]++; deg[v]++;
    }

    int mx = 0;
    for (int i = 1; i <= n; i++) mx = max(mx, deg[i]);
    if (mx > k) {
        cout << "NO\n";
        return 0;
    }

    vector<int> parent(n + 1, 0);
    vector<int> parColor(n + 1, 0);
    vector<int> order;
    order.reserve(n);

    // iterative DFS to get parent and order
    vector<int> st;
    st.reserve(n);
    st.push_back(1);
    parent[1] = -1;

    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        order.push_back(u);
        for (auto [v, id] : g[u]) {
            if (v == parent[u]) continue;
            parent[v] = u;
            st.push_back(v);
        }
    }

    vector<int> color(n); // 1..n-1 used
    for (int u : order) {
        int c = 1;
        for (auto [v, id] : g[u]) {
            if (v == parent[u]) continue;

            while (c == parColor[u]) c++;
            color[id] = c;
            parColor[v] = c;
            c++;
        }
    }

    cout << "YES\n";
    for (int i = 1; i <= n - 1; i++) {
        if (i > 1) cout << ' ';
        cout << color[i];
    }
    cout << "\n";
    return 0;
}