Codeforces Round #547 (Div. 3) G. Privatization of Roads in Treeland(BFS，貪心)

題目連結：http://codeforces.com/contest/1141/problem/G

題意：現有一棵樹，n個節點，n-1條邊，你可以選擇[1, r]中選數标在邊上，和一個節點相連的邊不能有兩個标号一樣的，但是可以選擇k個節點打破這個規則，問r最小是多少。

解題心得：

1. 就是一個貪心，既然可以選擇k個節點打破規則，那肯定按照結點的度排序，那麼r就是降序節點中的第k-1個節點的度。然後将前k個節點标記一下。
2. 跑一個樹上bfs，如果遇到标記的節點，将所有和他相連的邊都标記成一個數，不然就循環标記。

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 100;

//規定在記錄邊的時候pair<int,int> 第一個節點的标号比第二個小

vector<int> ve[maxn];//鄰接表
vector<pair<int, int> > edge, degree;//記錄輸入順序的邊和每個節點的度
map<pair<int, int>, int> ans;//記錄最後每個邊标記的答案是多少
bool vis[maxn];//标記可以打破規則的節點
int n, k, R;

struct Last_edge {//記錄在BFS中目前節點的父節點，目前節點與父節點邊的标号，目前節點的父節點
    int u, num, pre;

    Last_edge() {};

    Last_edge(int u, int num, int pre) : u(u), num(num), pre(pre) {};
};

void init() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a > b) swap(a, b);
        edge.push_back(make_pair(a, b));
        ans[make_pair(a, b)] = -1;
        ve[a].push_back(b);
        ve[b].push_back(a);
    }
}

void checke_max_degree() {//按照節點度降序排列，找出R，标記可以打破規則的節點
    for (int i = 1; i <= n; i++) {
        degree.push_back(make_pair(ve[i].size(), i));
    }

    sort(degree.begin(), degree.end());
    reverse(degree.begin(), degree.end());

    for (int i = 0; i < k; i++) {
        int u = degree[i].second;
        vis[u] = true;
    }
    R = degree[k].first;
    printf("%d\n", R);
}

bool BFS() {
    queue<Last_edge> qu;
    qu.push(Last_edge(1, 0, -1));

    while (!qu.empty()) {
        Last_edge now = qu.front();
        qu.pop();

        int num = (now.num + 1) % (R + 1);
        if (num == 0) num = 1;
        for (int i = 0; i < ve[now.u].size(); i++) {
            int v = ve[now.u][i];
            if(v == now.pre) continue;

            int a = now.u, b = v;
            if (a > b) swap(a, b);
            if (vis[now.u]) {
                qu.push(Last_edge(v, 1, now.u));
                ans[make_pair(a, b)] = 1;
                continue;
            }

            qu.push(Last_edge(v, num, now.u));
            ans[make_pair(a, b)] = num;
            num = (num + 1) % (R + 1);
            if (num == 0) num = 1;
        }
    }
}

int main() {
//    freopen("1.in", "r", stdin);
    init();

    checke_max_degree();

    BFS();

    for (int i = 0; i < edge.size(); i++) {
        int a = edge[i].first;
        int b = edge[i].second;
        if (a > b) swap(a, b);
        printf("%d ", ans[make_pair(a, b)]);
    }

    return 0;
}