Privatization of Roads in Treeland

发表于 2024-06-07 分类于 codeforces ， practice

Treeland包含n个城市和n-1条道路。每条道路都是双向的，连接两个不同的城市。从任何一个城市你都可以通过公路到达任何其他城市。是的，你是对的——这个国家的拓扑结构是一棵没有方向的树。

在Treeland有一些私人道路公司。政府决定向这些公司出售道路。每条路都属于一家公司，一家公司可以拥有多条道路。

政府害怕看上去不公平。他们认为，如果有一家公司拥有两条或两条以上的进入这个城市的道路，那么这个城市里的人就会认为这是不公平的。政府希望这样不公平的城市数量不超过k，那么最少需要多少个不同的公司来参与投资？

选择公司的数量r，这样就可以将每条道路分配给某家公司，这样一家公司拥有两条或两条以上到达同一个城市道路的城市数量最多为k。（译者注：这里是有一点费脑子，大家多想想）换句话说，如果对一个城市来说，所有的到达这座城市的道路都属于不同的公司，那么这个城市就是好的。你的任务是找到最小的r，然后分配所有道路，使得不太好的城市的数量不超过k。

图为第一个例子(n=6，k=2)。答案r=2。边上的数字表示边的编号。边的颜色表示公司：红色为第一个公司，蓝色为第二个公司。灰色顶点(3号)不好。这类顶点的数目(只有一个)不超过k（k=2）。如果有一家公司，在分配合理的情况下，不可能有2个不好的城市。

Privatization of Roads in Treeland

Created by LXC on Mon May 6 23:39:03 2024

https://codeforces.com/problemset/problem/1141/G

ranting: 1900

tag: binary search, constructive algorithms, dfs and similar, graphs, greedy, trees

problem

在Treeland有一些私人道路公司。政府决定向这些公司出售道路。每条路都属于一家公司，一家公司可以拥有多条道路。

solution

按照每个城市的度降序排序。所需要的公司数量就是第k+1个城市的度。

code


#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n, k;
    cin >> n >> k;
    vector<vector<pair<int,int>>> g(n);
    vector<int> d(n);
    for (int i=0; i<n-1; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        d[x]++;
        d[y]++;
        g[x].emplace_back(y, i);
        g[y].emplace_back(x, i);
    }
    sort(d.rbegin(), d.rend());
    int c = d[k];
    vector<int> ans(n-1);
    function<void(int,int,int)> dfs = [&](int u, int fa, int val) {
        for (auto [v, p]:g[u]) {
            if (v == fa) continue;
            ans[p] = (++val)%c;
            dfs(v, u, val);
        }
    };
    dfs(0, -1, c-1);
    cout << c << "\n";
    for (auto i:ans) {
        cout << i+1 << " ";
    }
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}