Codeforces Round 897 (Div. 2)

F. Most Different Tree

当 \(n=2\) 时，只能构造一条长度为 \(2\) 的链。

当 \(n\ge 3\) 时，对于 \(i\) \((1\le i\le n)\)，以 \(i\) 作为根的树记为 \(h_i\)，考虑枚举树找一个大小为 \(s\) 的树 \(t\)，使得不存在任何一个 \(h_i=t\)，且 \(s\) 尽可能小，然后从 \(1\) 连一条链到该数的根节点。

这样可以保证构造出来的以 \(1\) 到 \(t\) 为根的树都和所给的不同。

使用树 \(\text{hash}\)。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;
using u64 = unsigned long long;

const u64 mask = chrono::steady_clock::now().time_since_epoch().count();

u64 shift(u64 x) {
    x ^= mask;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    x ^= mask;
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    if (n == 2) {
        cout << "1 2\n";
        return 0;
    }

    unordered_set<u64> st(1024);
    st.max_load_factor(0.25);

    function<u64(int, int)> dfs = [&](int cur, int pre) {
        u64 h = 1;
        for (auto &nex : g[cur]) {
            if (nex != pre) {
                h += shift(dfs(nex, cur));
            }
        }
        st.insert(h);
        return h;
    };  

    dfs(0, -1);

    vector<vector<int>> b(n);

    function<u64(int)> TreeHash = [&](int cur) {
        u64 h = 1;
        for (auto &nex : b[cur]) {
            h += shift(TreeHash(nex));
        }
        return h;
    };

    for (int s = 2; s <= n; s++) {
        function<void(int, int)> get = [&](int cur, int pre) {
            if (cur == s) {
                if (st.count(TreeHash(0))) {
                    return;
                }

                for (int i = 1; i <= n - s; i++) {
                    cout << i << ' ' << i + 1 << '\n';
                } 

                for (int i = 0; i < s; i++) {
                    for (auto &j : b[i]) {
                        cout << i + n - s + 1 << ' ' << j + n - s + 1 << '\n';
                    }
                }
                exit(0);
            }

            for (int i = pre; i < cur; i++) {
                b[i].push_back(cur);
                get(cur + 1, i);
                b[i].pop_back();
            }
        };

        get(1, 0);
    }

    return 0;
}