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;
}