木の同型性判定プログラム

//木の同型性判定プログラム
//"Explanation for Tree isomorphism talk"と"木を隠すなら森の中"を参考にプログラミングしてみました。
//ソースコードはC++
//入力:頂点数n、(辺数n-1)、の二つの根なし無向木T1とT2
//出力:T1とT2が同型ならば"Yes"、そうでないならば"No"

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <cmath>

using namespace std;

const long long null = -1;

//tree
typedef vector< vector< long long > > Tree;
long long n;
long long m;
Tree T1;
Tree T2;

//centers of tree
vector<long long> nums;
long long max_num;
long long farthest_path_num;
long long r;
long long T1_farthest_vertex_1;
long long T1_farthest_vertex_2;
long long T2_farthest_vertex_1;
long long T2_farthest_vertex_2;
long long T1_center_1;
long long T1_center_2;
long long T2_center_1;
long long T2_center_2;

//isomorphism
unordered_map<string, long long> T1_name_num_1;
unordered_map<string, long long> T1_name_num_2;
unordered_map<string, long long> T2_name_num_1;
unordered_map<string, long long> T2_name_num_2;
vector<long long> T1_names_1;
vector<long long> T1_names_2;
vector<long long> T2_names_1;
vector<long long> T2_names_2;
long long num;
const long long max_digit_num = 10;

void dfs1(Tree T, long long v, long long num){
    for(long long i = 0; i < T[v].size(); i++){
        long long w = T[v][i];
        if(nums[w] == null){
            nums[w] = num+1;
            dfs1(T, w, num+1);
        }
    }
    return;
}

void radix_sort(vector<long long> &sub_names){
    vector<vector<long long>> bucket(10);
    for(long long d = 0, r = 1; d < max_digit_num; d++, r *= 10){
        for(long long i = 0; i < sub_names.size(); i++){
            long long key = (sub_names[i] / r) % 10;
            bucket[key].push_back(sub_names[i]);
        }
        for(long long j = 0, i = 0; j < 10; j++){
            if(!bucket[j].empty()){
                for(long long k = 0; k < bucket[j].size(); k++){
                    sub_names[i++] = bucket[j][k];
                }
            }
        }
        for(long long i = 0; i < 10; i++){
            bucket[i].clear();
        }
    }

    return;
}

void dfs2(Tree T, unordered_map<string, long long> &name_num, vector<long long> &names, long long v, long long pre_v, long long level){
    if(T[v].size() == 0){
        if(name_num.count("0") == 0){
            num++;
            name_num.emplace("0", num);
        }
        names[v] = name_num["0"];
        return;
    }

    vector<long long> sub_names;
    for(long long i = 0; i < T[v].size(); i++){
        long long w = T[v][i];
        if(names[w] == 0 && w != pre_v){
            dfs2(T, name_num, names, w, v, level+1);
            sub_names.push_back(names[w]);
        }
    }
    radix_sort(sub_names);
    string name = "";
    for(long long i = 0; i < sub_names.size(); i++){
        name += to_string(sub_names[i]);
    }

    if(name_num.count(name) == 0){
        num++;
        name_num.emplace(name, num);
    }
    names[v] = name_num[name];

    return;
}

int main(){

    cin >> n;
    m = n-1;

    T1.resize(n);
    T2.resize(n);
    for(long long i = 0; i < m; i++){
        long long v,w;
        cin >> v >> w;
        T1[v].push_back(w);
        T1[w].push_back(v);
    }
    for(long long i = 0; i < m; i++){
        long long v,w;
        cin >> v >> w;
        T2[v].push_back(w);
        T2[w].push_back(v);
    }

    //centers of tree
    nums.resize(n, null);
    T1_farthest_vertex_1 = null;
    T1_farthest_vertex_2 = null;
    T2_farthest_vertex_1 = null;
    T2_farthest_vertex_2 = null;
    T1_center_1 = null;
    T1_center_2 = null;
    T2_center_1 = null;
    T2_center_2 = null;

    //T1_farthest_vertex_1を求める
    nums.assign(n, null);
    nums[0] = 0;
    dfs1(T1, 0, 0);
    max_num = 0;
    for(long long i = 0; i < n; i++){
        if(max_num < nums[i]){
            max_num = nums[i];
            T1_farthest_vertex_1 = i;
        }
    }

    //T1_farthest_vertex_2を求める
    nums.assign(n, null);
    nums[T1_farthest_vertex_1] = 0;
    dfs1(T1, T1_farthest_vertex_1, 0);
    max_num = 0;
    for(long long i = 0; i < n; i++){
        if(max_num < nums[i]){
            max_num = nums[i];
            T1_farthest_vertex_2 = i;
        }
    }

    farthest_path_num = max_num;
    r = ceil(double(farthest_path_num)/2.0);
    //cout << "T1-r ->" << r <<endl;

    //T1_center_1を求める
    nums.assign(n, null);
    nums[T1_farthest_vertex_1] = 0;
    dfs1(T1, T1_farthest_vertex_1, 0);
    for(long long i = 0; i < n; i++){
        if(nums[i] == r){
            T1_center_1 = i;
            break;
        }
    }

    //T1_center_2を求める
    nums.assign(n, null);
    nums[T1_farthest_vertex_2] = 0;
    dfs1(T1, T1_farthest_vertex_2, 0);
    for(long long i = 0; i < n; i++){
        if(nums[i] == r){
            T1_center_2 = i;
            break;
        }
    }

    //T2_farthest_vertex_1を求める
    nums[0] = 0;
    nums.assign(n, null);
    dfs1(T2, 0, 0);
    max_num = 0;
    for(long long i = 0; i < n; i++){
        if(max_num < nums[i]){
            max_num = nums[i];
            T2_farthest_vertex_1 = i;
        }
    }

    //T2_farthest_vertex_2を求める
    nums.assign(n, null);
    nums[T2_farthest_vertex_1] = 0;
    dfs1(T2, T2_farthest_vertex_1, 0);
    max_num = 0;
    for(long long i = 0; i < n; i++){
        if(max_num < nums[i]){
            max_num = nums[i];
            T2_farthest_vertex_2 = i;
        }
    }

    farthest_path_num = max_num;
    r = ceil(double(farthest_path_num)/2.0);
    //cout << "T2-r ->" << r <<endl;

    //T2_center_1を求める
    nums.assign(n, null);
    nums[T2_farthest_vertex_1] = 0;
    dfs1(T2, T2_farthest_vertex_1, 0);
    for(long long i = 0; i < n; i++){
        if(nums[i] == r){
            T2_center_1 = i;
            break;
        }
    }

    //T2_center_2を求める
    nums.assign(n, null);
    nums[T2_farthest_vertex_2] = 0;
    dfs1(T2, T2_farthest_vertex_2, 0);
    for(long long i = 0; i < n; i++){
        if(nums[i] == r){
            T2_center_2 = i;
            break;
        }
    }

    /*
    //確認用
    cout << "T1 : " << endl;
    for(long long i = 0; i < n; i++){
        cout << i << " : ";
        for(long long j = 0; j < T1[i].size(); j++){
            cout << T1[i][j] << " ";
        }cout << endl;
    }cout << endl;

    cout << "T2 : " << endl;
    for(long long i = 0; i < n; i++){
        cout << i << " : ";
        for(long long j = 0; j < T2[i].size(); j++){
            cout << T2[i][j] << " ";
        }cout << endl;
    }cout << endl;

    cout << "farthest_vertexs" << endl;
    cout << "T1_farthest_vertex_1 -> " << T1_farthest_vertex_1 <<endl;
    cout << "T1_farthest_vertex_2 -> " << T1_farthest_vertex_2 <<endl;
    cout << "T2_farthest_vertex_1 -> " << T2_farthest_vertex_1 <<endl;
    cout << "T2_farthest_vertex_2 -> " << T2_farthest_vertex_2 <<endl;

    cout << "centers : " << endl;
    cout << "T1_center_1 -> " << T1_center_1 << endl;
    cout << "T1_center_2 -> " << T1_center_2 << endl;
    cout << "T2_center_1 -> " << T2_center_1 << endl;
    cout << "T2_center_2 -> " << T2_center_2 << endl;
    */

    //isomorphism
    T1_names_1.resize(n, 0);
    T1_names_2.resize(n, 0);
    T2_names_1.resize(n, 0);
    T2_names_2.resize(n, 0);
    
    num = 0;
    dfs2(T1, T1_name_num_1, T1_names_1, T1_center_1, null, 0);
    num = 0;
    dfs2(T1, T1_name_num_2, T1_names_2, T1_center_2, null, 0);
    num = 0;
    dfs2(T2, T2_name_num_1, T2_names_1, T2_center_1, null, 0);
    num = 0;
    dfs2(T2, T2_name_num_2, T2_names_2, T2_center_2, null, 0);

    /*
    //確認用
    cout << "names : " << endl;
    cout << "T1_names_1[T1_center_1] -> " << T1_names_1[T1_center_1] << endl;
    cout << "T1_names_2[T1_center_2] -> " << T1_names_2[T1_center_2] << endl;
    cout << "T2_names_1[T2_center_1] -> " << T2_names_1[T2_center_1] << endl;
    cout << "T2_names_2[T2_center_2] -> " << T2_names_2[T2_center_2] << endl;
    */

    if(T1_names_1[T1_center_1] == T2_names_1[T2_center_1] || T1_names_1[T1_center_1] == T2_names_2[T2_center_2]){
        cout << "Yes" << endl;
    }else if(T1_names_2[T1_center_2] == T2_names_1[T2_center_1] || T1_names_2[T1_center_2] == T2_names_2[T2_center_2]){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}