题目链接:https://codeforces.com/contest/1141/problem/G

题解:我们不妨考虑每个点的度数indind,那么当k==0k == 0是很显然此时答案应为max(ind[i])max(ind[i]),(类似于抽屉原理的思维),那么当k>0k > 0时 答案很显然为第k+1k + 1大的点的度数。那么我们只需要确定一个答案之后,直接对图染色即可。(染色必然是可行的,在已知答案的情况下)

总结: 对于边染色的情况,可以考虑度数的问题来解决

#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 5;
struct edge {
    int u,v,next;
}e[N * 2];
int head[N * 2],vis[N],cnt,col[N * 2],ind[N];
int n,k,ans;
void insert(int u, int v) {
    e[++cnt].u = u; e[cnt].v = v; e[cnt].next = head[u]; head[u] = cnt;
}
void dfs(int u, int d) {
    vis[u] = 1;
    for(int i = head[u]; i ; i = e[i].next) {
        int v = e[i].v;
        if(!vis[v]) {
            vis[v] = 1;
            d = (d + 1) % ans;
            col[(i % 2 ? i : i - 1)] = d;
            dfs(v, d);
        }
    }
}
int main() {
    cin >> n >> k;
    for(int i = 1; i <= n - 1; i++) {
        int u,v;
        cin >> u >> v;
        insert(u, v); insert(v, u);
        ind[v]++; ind[u]++;
    }
    sort(ind + 1, ind + n + 1);
    cout << ind[n - k] << "\n";;
    ans = ind[n - k];
    dfs(1, 0);
    for(int i = 1; i <= 2 * (n - 1); i++) {
        if(i & 1) {
            cout << col[i] + 1<< " ";
        }
    }
    return 0;
}