生成一棵树

可以说包含大多数可以叉人的树。

code:

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

std::mt19937 g(static_cast<u32>(std::chrono::system_clock::now().time_since_epoch().count()));
const int Rand(int l, int r) {
    return g() % (r - l + 1) + l;
}
struct Tree {
    int n;
    std::vector<std::array<int, 2>> edges;
    Tree() {
        n = 0;
    }
    Tree(int _n) {
        n = _n;
        edges.clear();
    }
    void addEdge(int u, int v) {
        edges.push_back({u, v});
    }
    void printEdges(int beg = 1) {
        for (auto [u, v] : edges) {
            std::cout << u + beg << " " << v + beg << "\n";
        }
    }
} ;
void Merge(Tree &a, const Tree &b, int u, int v) {
    const int n = a.n;
    a.n += b.n;
    for (auto [u, v] : b.edges) {
        u += n, v += n;
        a.addEdge(u, v);
    }
    a.addEdge(u, v + n);
}
class TreeGenerator {
public:
    Tree Shuffle(Tree t) {
        std::vector<int> p(t.n);
        iota(p.begin(), p.end(), 0);
        shuffle(p.begin(), p.end(), g);
        for (auto& [u, v] : t.edges) {
            u = p[u];
            v = p[v];
            if (Rand(0, 1)) {
                std::swap(u, v);
            }
        }
        shuffle(t.edges.begin(), t.edges.end(), g);
        return t;
    }
    Tree Random(int n) {
        Tree t(n);
        for (int i = 1; i < n; ++i) {
            t.addEdge(i, Rand(0, i - 1));
        }
        return t;
    }
    Tree Random(int n, int d) {
        Tree t(n);
        for (int i = 1; i < n; ++i) {
            t.addEdge(i, Rand(std::max(0, i - d), i - 1));
        }
        return t;
    }
    Tree PruferToTree(std::vector<int> p) {
        int n = p.size() + 2;
        Tree t(n);

        std::vector<int> deg(n, 1);
        std::set<int> s;
        for (int i = 0; i < n - 2; ++i) {
            ++deg[p[i]];
        }
        for (int i = 0; i < n; ++i) {
            if (deg[i] == 1) {
                s.insert(i);
            }
        }

        for (int i = 0; i < n - 2; ++i) {
            int u = p[i], v = *s.begin();
            t.addEdge(u, v);
            s.erase(s.begin());
            --deg[u], --deg[v];

            if (deg[u] == 1) {
                s.insert(u);
            }
        }
        t.addEdge(*s.begin(), *--s.end());

        return t;
    }
    Tree RandomPruffer(int n) {
        std::vector<int> p(n - 2);
        for (int i = 0; i < n; ++i) {
            p[i] = Rand(0, n - 1);
        }
        return PruferToTree(p);
    }
    Tree Chain(int n) {
        return Dandelion(n, 1);
    }
    Tree Star(int n) {
        return Dandelion(n, n - 1);
    }
    Tree Binary(int n) {
        Tree t(n);
        std::vector<int> deg(n, 1), p(n - 2);
        for (int i = 0; i < n - 2; ++i) {
            int u = Rand(0, n - 1);
            while (deg[u] == 3) {
                u = Rand(0, n - 1);
            }
            p[i] = u;
        }
        return PruferToTree(p);
    }
    Tree CompleteBinary(int n) {
        assert(n & 1);
        Tree t(n);
        for (int i = 0; i < n - 1; ++i) {
            t.addEdge(i / 2, i + 1);
        }
        return t;
    }
    Tree Dandelion(int n, int d) {
        assert(d < n);
        Tree t(n);
        for (int i = 1; i <= d; ++i) {
            t.addEdge(i, 0);
        }
        for (int i = d + 1; i < n; ++i) {
            t.addEdge(i, i - d);
        }
        return t;
    }
    Tree Broom(int n, int d) {
        assert(d < n);
        Tree t(n);
        for (int i = 1; i <= d; ++i) {
            t.addEdge(i - 1, i);
        }
        for (int i = d + 1; i < n; ++i) {
            t.addEdge(0, i);
        }
        return t;
    }
    Tree Worm(int n) {
        Tree t(n);
        for (int i = 1; i < n; ++i) {
            if (i & 1) {
                t.addEdge(i - 1, i);
            } else {
                t.addEdge(i - 2, i);
            }
        }
        return t;
    }
} ;

int FindDiameter(Tree t) {
    int n = t.n;
    std::vector<std::vector<int>> adj(n);
    for (auto [u, v] : t.edges) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    auto bfs = [&](int st) {
        std::queue<int> q;
        std::vector<int> dis(n, -1);
        dis[st] = 0;
        q.push(st);

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (auto v : adj[u]) {
                if (dis[v] == -1) {
                    dis[v] = dis[u] + 1;
                    q.push(v);
                }
            }
        }

        return std::make_pair(max_element(dis.begin(), dis.end()) - dis.begin(), dis);
    } ;
    int a = bfs(0).first;
    auto [b, dis] = bfs(a);

    return dis[b];
}

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

    /*下面展示了一下将若干个大小为 1E3 的菊花图的根节点拼成一条链*/
    TreeGenerator gen;
    int n = 1E3;
    std::vector<Tree> tr(n);
    for (int i = 0; i < n; ++i) {
        tr[i] = gen.Star(1E3);
    }
    Tree t = tr[0];
    for (int i = 1; i < n; ++i) {
        Merge(t, tr[i], t.n - 1E3, 0);
    }
    std::cout << "n: " << t.n << ", d: " << FindDiameter(t) << "\n";
    t.printEdges();

    return 0;
}