icpc-klingons.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

typedef long long ll;

const int MAX_M = 10000;
const int MAX_N = 10000;

struct node {
    int sup;
    char f;
    int i;

    node *parent;
    vector<node *> children;
    int num_subordinates = 0;

    node () {}
    node (char fs, int s, int idx) {
        f = fs;
        sup = s;
        i = idx;
    }

    ll hash() {
        return ((ll) children.size() * 52 * MAX_M) + ((ll) num_subordinates * 26) + f - 66;
    }
};

typedef vector<node *> vn;
typedef vector<bool> vb;

void count_subordinates(node* root) {
    int s = 0;
    for(int i = 0; i < root->children.size(); i++) {
        count_subordinates(root->children[i]);
        s += root->children[i]->num_subordinates + 1;
    }

    root->num_subordinates = s;
}

int best = 0;

void match_tree (node* root, vector<vb> &matches, map<ll, vn> &nmap) {
    for(int i = 0; i < root->children.size(); i++) {
        match_tree(root->children[i], matches, nmap);
    }

    ll h = root->hash();
    int root_idx = root->i;

    // definitely no match for me
    if (nmap.find(h) == nmap.end()) return;

    bool good;

    for (int i = 0; i < nmap[h].size(); i++) {
        int n_idx = nmap[h][i]->i;
        good = true;

        for (int c = 0; c < root->children.size(); c++) {
            int c_idx = root->children[c]->i;
            int nc_idx = nmap[h][i]->children[c]->i;

            if (! matches[c_idx][nc_idx]) {
                good = false;
                break;
            }
        }

        if (good) {
            matches[root_idx][n_idx] = true;
            if (root->num_subordinates + 1 > best) {
                best = root->num_subordinates + 1;
            }
        }
    }
}

int main () {
    int t;
    cin >> t;
    for(; t > 0; t--) {
        int M, N;
        cin >> M >> N;

        vector<node> m_soldiers;
        vector<node> n_soldiers;

        for (int i = 0; i < M; i++) {
            char f;
            int s;
            cin >> f >> s;
            m_soldiers.push_back(node(f, s, i));
        }
        for (int i = 0; i < N; i++) {
            char f;
            int s;
            cin >> f >> s;
            n_soldiers.push_back(node(f, s, i));
        }

        // link the btrees
        for (int i = 0; i < M; i++) {
            if (m_soldiers[i].sup >= 0) {
                node *parent = &m_soldiers[m_soldiers[i].sup];
                m_soldiers[i].parent = parent;
                parent->children.push_back(&m_soldiers[i]);
            }
        }

        for (int i = 0; i < N; i++) {
            if (n_soldiers[i].sup >= 0) {
                node *parent = &n_soldiers[n_soldiers[i].sup];
                n_soldiers[i].parent = parent;
                parent->children.push_back(&n_soldiers[i]);
            }
        }

        node* m_root = &m_soldiers[0];
        node* n_root = &n_soldiers[0];

        // count the number of subordinates of each
        count_subordinates(m_root);
        count_subordinates(n_root);

        // hash n_tree
        map<ll, vn> nmap;
        for (int i = 0; i < N; i++) {
            node* n = &n_soldiers[i];
            ll h = n->hash();
            if (nmap.find(h) == nmap.end()) {
                vector <node *> v;
                nmap[h] = v;
                nmap[h].push_back (n);
            } else {
                nmap[h].push_back(n);
            }
        }

        // initialize matches
        vector<vb> matches(M, vector<bool> (N, false));

        best = 0;
        match_tree(m_root, matches, nmap);
        cout << best << endl;
    }

    return 0;
}