题解：AT_kupc2020_i Coloring Paths

· · 题解

我们充分发扬人类智慧。如果你对最重的边叫甲边，第二重的边叫乙边，其他边叫丙边，那么每个点从下往上都最多经过 \log_3 n 条丙边。所以你对所有丙边单独编号，前两种边共用三个编号（为什么是三个编号？因为重儿子也需要一个单独的重编号），那么最后路径颜色数卡满就是 k+\log_k n + 1\le 12，其中 k 是儿子种类数。非常不优秀，但是不知道为什么过了。

那咋办，咱依旧是新手爱记录，投上来吧。至少有个管理组提示 tag 比较漂亮。

有个更乱搞的做法是遍历 k\in[3,6]，但是没写，因为不知道上界，如果有大手子可以分析一下。这里代码的做法是随机了 20 个根，AI 分析它的错误率只有 \le 0.05\%。

#include <bits/stdc++.h>
//#define int long long
using namespace std;
#define fi first 
#define se second
using pii = pair <int, int>;
const int N = 2e4;
int n, m, dfn [N + 5], fid [N + 5], fa [N + 5], x [N + 5], y [N + 5],
    siz [N + 5], col [N + 5], tot, new_id;
vector <pii> G [N + 5], H [N + 5], T [N + 5];
unordered_set <int> w [N + 5];
mt19937 RND (time (0));
void dfs (int u) {
    siz [u] = 1; dfn [u] = ++ new_id;
    for (auto [to, id] : G [u]) if (to ^ fa [u]) {
        if (!dfn [to]) {
            H [u]. push_back ({to, id});
            fa [to] = u; fid [to] = id;
            dfs (to); siz [u] += siz [to];
        } else if (dfn [to] < dfn [u]) {
            T [to]. push_back ({u, id});
        }
    }
    sort (H [u]. begin (), H [u]. end (), [] (pii x, pii y) -> bool {
        return siz [x. fi] > siz [y. fi];
    });
}
void Dfs (int u) {
    for (int i = 0 ; i < H [u]. size () ; i ++) {
        auto [to, id] = H [u] [i];
        if (i == 0) col [id] = (col [fid [u]] == 1 ? 2 : 1);
        else if (i == 1) col [id] = (col [fid [u]] == 3 ? 2 : 3);
        if (col [id] == 3) tot = 3;
    }
    for (auto [to, id] : H [u]) Dfs (to);
}
int subtree (int u, int v) {
    return dfn [u] <= dfn [v] && dfn [v] < dfn [u] + siz [u];
}
int ranint (int a, int b) {
    return a + RND () % (b - a + 1);
}
signed main () {
    ios :: sync_with_stdio (0); cin. tie (0); cout. tie (0);
    cin >> n >> m; tot = 2;
    for (int i = 1 ; i <= m ; i ++) {
        cin >> x [i] >> y [i];
        G [x [i]]. push_back ({y [i], i});
        G [y [i]]. push_back ({x [i], i}); 
    }
    for (int k = 0 ; k < 20 ; k ++) {
        for (int i = 1 ; i <= m ; i ++) col [i] = 0;
        for (int i = 1 ; i <= n ; i ++)
            H [i]. clear (), T [i]. clear (), dfn [i] = 0;
        int root = ranint (1, n); tot = 2; new_id = 0;
        int flag = 1; fa [root] = fid [root] = 0;
        dfs (root); Dfs (root);
        for (int i = 1 ; i <= m ; i ++)
            if (!col [i]) col [i] = ++ tot;
        for (int i = 1 ; i <= m ; i ++) {
            auto &s = w [i]; s. clear ();
            int u = x [i], v = y [i];
            if (dfn [u] < dfn [v]) swap (u, v);
            if (fa [u] == v) {
                int j = 0, p;
                while (1) {
                    for (auto [to, id] : T [v])
                        if (subtree (u, to)) {
                            j = to; p = id; 
                            break ;
                        }
                    if (j) break ;
                    s. insert (col [fid [v]]);
                    v = fa [v];
                }
                s. insert (col [p]);
                while (j != u) {
                    s. insert (col [fid [j]]);
                    j = fa [j];
                }
            } else {
                while (u != v) {
                    s. insert (col [fid [u]]);
                    u = fa [u];
                }
            }
            if (s. size () > 8)
                { flag = 0; break ; }
        } if (!flag) continue ;

        for (int i = 1 ; i <= m ; i ++)
            cout << col [i] << " \n" [i == m];
        for (int i = 1 ; i <= m ; i ++) {
            auto &s = w [i];
            cout << s. size () << " ";
            for (auto x : s) cout << x << " ";
            cout << endl;
        }
        return 0;
    }
}