Codeforces Round #547 (Div. 3) G. Privatization of Roads in Treeland（二分+dfs）

题目链接

题意

一个无向无环连通图，你要给边染色，连接同一个节点的边染色相同记为坏点，可以存在坏点个数不超过k个，求最小染色种类及方案

思路

预处理每个节点度数，二分染色种类数，度数大于种类数即坏点，否则必定可以正常染色。

知道答案后，dfs一下就好，dfs多传一个参记录上条边啥颜色。

（彩笔比赛只a了三道，发现自己找bug能力不足，容易写出沙雕bug）

代码

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

int d[200005], bel[200005], n, k, vis[200005], ans;
vector<pair<int,int>> e[200005];

int f(int mid)
{
    int cnt = 0;
    for(int i = 1; i <= n; ++i) if(d[i] > mid) ++cnt;
    return cnt <= k;
}

void dfs(int u, int col)
{
    vis[u] = 1;
    int cnt = 1;
    for(auto v : e[u])
    {
        if(vis[v.first]) continue;
        if(cnt == col) ++cnt;
        if(cnt > ans) cnt = 1;
        bel[v.second] = cnt;
        dfs(v.first, cnt);
        ++cnt;
        if(cnt > ans) cnt = 1;
    }
}

int main()
{
    int u, v;
    scanf("%d%d",&n,&k);
    for(int i = 1; i < n; ++i)
    {
        scanf("%d%d",&u,&v);
        e[u].push_back(make_pair(v,i));
        e[v].push_back(make_pair(u,i));
        ++d[u], ++d[v];
    }
    int mid, l = 1, r = n;
    while(l <= r)
    {
        mid =(l+r) >> 1;
        if(f(mid)) r = mid-1, ans = mid;
        else l = mid+1;
    }
    dfs(1,-1);
    printf("%d\n",ans);
    for(int i = 1; i < n; ++i) printf("%d ",bel[i]);
    return 0;
}