AGC024 D: Isomorphism Freak

入力例ですこし試してみると、頂点を追加していってグラフをできるだけ対称的にする、という問題であることに気づきます。

対称中心は、ノードになることもありますし、辺の中心にになることもあるので、インプット時にダミーの頂点を各辺の間に追加しておきます。

long tmp = 100;
REP(i,n-1) {
    long a, b;
    cin >> a >> b;
    a--; b--;
    long mid = tmp;
    tmp++;
    adj[a].push_back(mid);
    adj[mid].push_back(a);
    adj[mid].push_back(b);
    adj[b].push_back(mid);
}

あとは、ダミーを含め、どの頂点を中心にするかを決め打ちして調べます。 中心は明らかに次数2以上なので、葉は飛ばします。

次のコードは、頂点iを中心としたときの、（カラフルさ、葉の数）のペアを返します。

対称となるようにノードを追加したあと、木がどうなっているかというと、木を頂点iを根とした根付き木とみなしたときに、葉でない任意のノードについて、それらの子がすべて同型となっています。

このときカラフルさは、木の深さに等しく、葉の数は、頂点から葉に向かうパス上で発生する分岐の数の積に等しいです。木の深さは、2で割ってやることで、ダミーを除いた深さを考えます。

実装では、根を中心とし、BFSで頂点を見ていき、一つのパスにまとめています（上述したことからわかりますが、ノードを追加したのちのグラフにおいて、根から葉に向かうパスはすべて同じ長さとなるので一つにまとめることができます）。

// pair of (color, leaves)
P cnt(int i) {
    reset(); // set false to visited
    long div = adj[i].size();
    long depth = 0;
    VI cur;
    visited[i] = true;
    cur.push_back(i);
    while (1) {
        VI nex;
        long maxdeg = 1;
        for (auto j: cur) {
            maxdeg = max(maxdeg, long(adj[j].size() - 1));
            for (auto k: adj[j]) {
                if (!visited[k]) {
                    nex.push_back(k);
                    visited[k] = true;
                }
            }
        }
        
        if (nex.size() == 0) {
            return P(depth / 2 + 1, div);
        }
        cur = VI(nex);
        
        div *= maxdeg;
        depth++;
    }
    exit(1);
}