题解：AT_agc024_d [AGC024D] Isomorphism Freak

· · 题解

想了一万年 O(n) 然后发现 n\le 100，气笑了。

第一问是简单的，对满二叉树调整一下就行了，容易发现若直径长度为 d 则奇偶分类后可得答案为 \lceil \frac d2\rceil。第二问考虑先随便定一个根，记录 mx_d 表示树上深度为 d 的点儿子数量最大值是多少，h 表示树的最大深度，则为了满足条件数上每一层所有结点的儿子数量都必须相同，叶子总数就是 \prod\limits_{i=1}^{h-1}mx_i，然后如果选择一条边作为中心那么可以看作是把边断开然后两个同构的树每一层结点子结点数量都相同，叶子总数就是 2\prod\limits_{i=1}^{h-1}mx_i，直接枚举结点 / 边作为根可以做到平方时间复杂度。比较好奇能不能做到更优（问了一下 gpt 是可以的，但是不想写了）

代码写的平方。

namespace lowspeed_song {

mt19937_64 mt(time(0));

inline void init() {
}

vector<int> adj[N];
pair<int, int> e[N];

int dep[N], mx[N], high;

inline void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    int cnt = 0;
    for (int &v : adj[u]) if (v != fa) dfs(v, u), ++cnt;
    mx[dep[u]] = max(mx[dep[u]], cnt);
}

inline void sol([[maybe_unused]]int __testcase_id, [[maybe_unused]]int __testcase_sum) {
    int n; cin >> n;
    for (int i = 1; i < n; ++i) {
        int a, b; cin >> a >> b, e[i] = {a, b};
        adj[a].emplace_back(b), adj[b].emplace_back(a);
    } pair<int, int> res = {inf, inf};
    for (int i = 1; i <= n; ++i) {
        memset(mx, 0, sizeof mx);
        dfs(i, 0), high = *max_element(dep + 1, dep + n + 1);
        int oo = 1; for (int i = 1; i < high; ++i) oo = oo * mx[i];
        res = min(res, pair{high, oo});
    } for (int i = 1; i < n; ++i) {
        memset(mx, 0, sizeof mx);
        memset(dep, 0, sizeof dep);
        auto [u, v] = e[i];
        dfs(u, v); int _ = dep[u]; dep[u] = 0;
        dfs(v, u), dep[v] = _, high = *max_element(dep + 1, dep + n + 1);
        int oo = 2; for (int i = 1; i < high; ++i) oo = oo * mx[i];
        res = min(res, pair{high, oo});
    } cout << res.first << ' ' << res.second << '\n';
}

} // namespace lowspeed_song