AT_agc024_d [AGC024D] Isomorphism Freak 题解

Linurve10 · 2026-11-13 16:58:18 · 题解

设直径长度为 l，第一问答案为 \lceil\frac{l}{2}\rceil。证明如下：

首先答案的下界是 \lceil\frac{l}{2}\rceil。

考虑一条链，此时中间位置是一个点或一条边。

• 如果是一个点，以它为根，对相同深度的点染同种颜色，即可达成同构要求，答案为 \lceil\frac{l}{2}\rceil，此时加入点只会使深度增加。
• 如果是一条边，将这条边断开，将两个端点连向一个新建的根节点，忽略根，染色方案同上即可取到 \lceil\frac{l}{2}\rceil。同样的，此时加入点不优。

所以答案下界为 \lceil\frac{l}{2}\rceil。

现在考虑一般的情况，取树的直径，将其视为上面的链。设深度为 x 的点中儿子数的最大值为 mx_x，深度最大值为 maxdep，我们发现如果依次将深度为 x={1,2,3\dots maxdep} 的点的儿子数全部增加至 mx_x，那么对于链的染色方案仍然是适用的。所以答案一定可以取到下界 \lceil\frac{l}{2}\rceil。

第二问的答案就是统计上面这种构造方法的叶子个数。证明如下：

如果同一个深度的点要满足同构要求，那么它们的子树应当同构，由于只能增加节点，所以每一个点的儿子数至少要增加到 mx_x，于是这种构造方案就是最优的。

接下来我们只要计算 \prod_{x=1}^{maxdep-1}mx_x 即为当前中心点或边的第二问答案。

由于 n\le100，枚举作为中心的点或边计算，取最小值即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105,inf=1e18;
int n,m;
int ans1=inf,ans2=inf;
int maxn[N],dep[N],maxdep;
struct node{int x,y;}e[N];
vector<int> vec[N];
void dfs(int x,int fa){
    dep[x]=dep[fa]+1;
    maxdep=max(maxdep,dep[x]);
    int cnt=0;
    for(int u:vec[x]){
        if(u==fa) continue;
        cnt++;
        dfs(u,x);
    }
    maxn[dep[x]]=max(maxn[dep[x]],cnt);
}
signed main(){
    // freopen("isomorphism.in","r",stdin);
    // freopen("isomorphism.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1,x,y;i<n;i++){
        scanf("%lld%lld",&x,&y);
        e[i]={x,y};
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        dfs(i,0);
        int cur=1;
        for(int j=1;j<maxdep;j++) cur*=maxn[j];
        if(maxdep<ans1) ans1=maxdep,ans2=cur;
        else if(maxdep==ans1) ans2=min(ans2,cur);
        for(int j=1;j<=n;j++) maxn[j]=dep[j]=0;
        maxdep=0;
    }
    for(int i=1;i<n;i++){
        int x=e[i].x,y=e[i].y,curdep=0,cur=2;
        dfs(x,y),curdep=dep[x],dep[x]=0;
        dfs(y,x),dep[y]=curdep;
        maxdep=0;
        for(int j=1;j<=n;j++) maxdep=max(maxdep,dep[j]);
        for(int j=1;j<maxdep;j++) cur*=maxn[j];
        if(maxdep<ans1) ans1=maxdep,ans2=cur;
        else if(maxdep==ans1) ans2=min(ans2,cur);
        for(int j=1;j<=n;j++) maxn[j]=dep[j]=0;
        maxdep=0;
    }
    printf("%lld %lld\n",ans1,ans2);
    return 0;
}