fork(1) download

copy

#include <bits/stdc++.h>
#include "testlib.h"
 
using namespace std;
using namespace std::chrono;
 
const int DEBUG_MODE = 0;
const int MODE = DEBUG_MODE;
const string LOG_FILE = "log.txt";
const double eps = 1e-9;
const double INF = 1e15;
 
struct Graph {
    int n;
	vector<vector<pair<int, double>>> adj;
    vector<vector<bool>> adj_matrix;
    vector<vector<double>> weight_matrix;
 
    void init(int _n) {
        assert(_n > 0);
        n = _n;
        adj = vector<vector<pair<int, double>>>(n, vector<pair<int, double>>());
        adj_matrix = vector<vector<bool>>(n, vector<bool>(n, false));
        weight_matrix = vector<vector<double>>(n, vector<double>(n, 0.0));
    }
 
    Graph() {
        n = 0;
        adj.clear();
    }
 
    Graph(int _n) {
        assert(_n > 0);
        init(_n);
    }
 
    void add_edge(int u, int v, double weight) {
        assert((0 <= min(u, v)) && (max(u, v) < n));
        adj[u].push_back(make_pair(v, weight));
        adj[v].push_back(make_pair(u, weight));
        weight_matrix[u][v] = weight_matrix[v][u] = weight;
        adj_matrix[u][v] = adj_matrix[v][u] = true;
    }
 
    int get_deg(int u) {
        assert((0 <= u) && (u < n));
        return adj[u].size();
    }
 
    bool have_edge(int u, int v) {
        assert((0 <= min(u, v)) && (max(u, v) < n));
        return adj_matrix[u][v];
    }
 
    double get_weight(int u, int v) {
        assert((0 <= min(u, v)) && (max(u, v) < n));
        return weight_matrix[u][v];
    }
};
 
struct Tree {
    int n, root;
    vector<int> par, subtree;
    vector<vector<int>> child;
    vector<vector<bool>> adj_matrix;
 
    void init(int _n, int _root) {
        assert(_n > 0);
        assert((0 <= _root) && (_root < _n));
        n = _n; root = _root;
        assert((root >= 0) && (root < n));
        par = vector<int>(n, -1); subtree = vector<int>(n, 0);
        child = vector<vector<int>>(n, vector<int>());
        adj_matrix = vector<vector<bool>>(n, vector<bool>(n, false));
    }
 
    void append_child(int u, int v) {
        assert((0 <= min(u, v)) && (max(u, v) < n));
        child[u].push_back(v);
        par[v] = u;
        adj_matrix[u][v] = adj_matrix[v][u] = true;
    }
 
    void DFS(int u, int par, Graph &g) {
        subtree[u] = 1;
        for(pair<int, double> &e : g.adj[u]) {
            int v = e.first;
            if (v != par) {
                append_child(u, v);
                DFS(v, u, g);
                subtree[u] += subtree[v];
            }
        }
    }
 
    void init(Graph &g, int root) {
        assert((0 <= root) && (root < g.n));
        init(g.n, root);
        DFS(root, -1, g);
    }
 
    Tree() {}
    Tree(Graph &g, int root) {
        init(g, root);
    }
 
    int get_num_child(int u) {
        assert((0 <= u) && (u < n));
        return child[u].size();
    }
 
    int get_deg(int u) {
        assert((0 <= u) && (u < n));
        return child[u].size() + (par[u] != -1);
    }
 
    bool have_edge(int u, int v) {
        assert((0 <= min(u, v)) && (max(u, v) < n));
        return adj_matrix[u][v];
    }
};
 
const int MAXQ = 100 + 10;
const int MAXG = 100 + 10;
 
//input data
Graph G, Q_graph;
Tree Q_tree;
int n_ins; double per_ins;
int n_del; double per_del;
double similar_score[MAXQ][MAXG];
double threshold = 0.0;
 
//variables for algorithm
int n_duplications;
int n_colors;
int color[MAXG];
 
//match result
double best_match_score;
vector<int> inserted_nodes;
vector<int> map_to;
 
void init_log() {
    ofstream lf(LOG_FILE);
    lf.close();
}
 
inline void write_log(string message) {
    ofstream lf(LOG_FILE, std::ofstream::app);
    lf << message;
    lf.close();
}
 
bool homologous(int q, int v) {
    return similar_score[q][v] >= threshold;
}
 
int get_bit(int x, int n) {
    return ((x >> n) & 1);
}
 
namespace feedback_vertex_set {
    bool DFS(Graph &g, int u, int par, int removed_vertices, vector<bool> &visited) {
        if (visited[u])
            return true;
        visited[u] = true;
        for(pair<int, double> &p : g.adj[u]) {
            int v = p.first;
            if ((v != par) && (get_bit(removed_vertices, v) == 0)) {
                if (DFS(g, v, u, removed_vertices, visited))
                    return true;
            }
        }
        return false;
    }
 
    bool is_feedback_vertex_set(Graph &g, int vertex_set) {
        vector<bool> visited(g.n, false);
        for(int v = 0; v < g.n; ++v)
            if ((!visited[v]) && (get_bit(vertex_set, v) == 0)) {
                bool cycle_found = DFS(g, v, -1, vertex_set, visited);
                if (cycle_found) return false;
            }
        return true;
    }
 
    vector<int> run(Graph &g) {
        for(int vertex_set = 0; vertex_set < (1 << g.n); ++vertex_set) {
            if (is_feedback_vertex_set(g, vertex_set)) {
                vector<int> feedback_vertex_set;
                for(int v = 0; v < g.n; ++v)
                    if (get_bit(vertex_set, v))
                        feedback_vertex_set.push_back(v);
                return feedback_vertex_set;
            }
        }
    }
}
 
int choose_root(Graph &g) {
    for(int i = 0; i < g.n; ++i)
        if (g.adj[i].size() == 1)
            return i;
    return -1;
}
 
namespace graph_to_tree {
    vector<int> dup_ver;
    vector<vector<int>> dup;
    vector<vector<bool>> existing_edges;
    vector<pair<int, int>> add_edges;
    vector<int> origin;
    int n_dup;
 
    int DFS(Graph &g, vector<vector<bool>> &existing_edges, int u, vector<int> &par, vector<bool> &visited) {
        if (visited[u])
            return u;
        visited[u] = true;
        for(pair<int, double> &p : g.adj[u]) {
            int v = p.first;
            if ((v != par[u]) && (existing_edges[u][v])) {
                par[v] = u;
                int x = DFS(g, existing_edges, v, par, visited);
                if (x >= 0) return x;
            }
        }
        return -1;
    }
 
    vector<int> find_a_cycle(Graph &g, vector<vector<bool>> &existing_edges) {
        vector<int> par(g.n, -1);
        vector<bool> visited(g.n, false);
        for(int v = 0; v < g.n; ++v)
            if (!visited[v]) {
                int u = DFS(g, existing_edges, v, par, visited);
                if (u >= 0) {
                    vector<int> c;
                    int x = par[u];
                    while (x != u) {
                        c.push_back(x);
                        x = par[x];
                    }
                    c.push_back(u);
                    return c;
                }
            }
        return vector<int>();
    }
 
    int choose_duplicated_vertex(vector<int> &feedback_vertex_set, vector<int> &cycle) {
        for(int u : feedback_vertex_set)
            for(int v : cycle)
                if (u == v)
                    return u;
        return -1;
    }
 
    int choose_neighbor_of_duplicated_node(Graph &g, int dup_ver, vector<int> &cycle, vector<vector<bool>> &existing_edges) {
        for(pair<int, double> &p : g.adj[dup_ver]) {
            int u = p.first;
            if (existing_edges[dup_ver][u]) {
                for(int v : cycle)
                    if (u == v)
                        return u;
            }
        }
        return -1;
    }
 
    Tree create_tree(Graph &g) {
        Graph g_tree(g.n + n_dup);
        for(int u = 0; u < g.n; ++u)
            for(int v = u + 1; v < g.n; ++v)
                if (existing_edges[u][v])
                    g_tree.add_edge(u, v, 0.0);
        for(pair<int, int> &e : add_edges)
            g_tree.add_edge(e.first, e.second, 0.0);
        int root = choose_root(g_tree);
        Tree tree(g_tree, root);
        for(int i = 0; i < g_tree.n; ++i)
            for(int j = i + 1; j < g_tree.n; ++j)
                if (g_tree.have_edge(i, j))
                    cout << "edge = " << i << " " << j << endl;
        return tree;
    }
 
    Tree run(Graph &g, vector<int> feedback_vertex_set) {
        dup = vector<vector<int>>(g.n, vector<int>());
        existing_edges = g.adj_matrix;
        add_edges.clear();
        n_dup = 0;
        origin.resize(g.n);
        for(int v = 0; v < g.n; ++v) origin[v] = v;
        while (true) {
            vector<int> cycle = find_a_cycle(g, existing_edges);
            if (cycle.size() == 0) break;
            cout << "cycle = "; for(int c : cycle) cout << c << " "; cout << "\n";
            int dup_ver = choose_duplicated_vertex(feedback_vertex_set, cycle);
            cout << "dup_ver = " << dup_ver << endl;
            assert(dup_ver >= 0);
            int nei = choose_neighbor_of_duplicated_node(g, dup_ver, cycle, existing_edges);
            cout << "nei = " << nei << "\n";
            assert(nei >= 0);
            cout << "index of new vertex = " << g.n + n_dup << endl;
            existing_edges[dup_ver][nei] = existing_edges[nei][dup_ver] = false;
            dup[dup_ver].push_back(g.n + n_dup);
            add_edges.push_back(make_pair(nei, g.n + n_dup));
            origin.push_back(dup_ver);
            ++n_dup;
        }
 
        dup_ver.resize(0);
        for(int v = 0; v < g.n; ++v)
            if (dup[v].size() > 0)
                dup_ver.push_back(v);
        return create_tree(g);
    }
}
 
bool can_delete_general(int q) {
    return Q_graph.get_deg(q) == 2;
}
 
bool can_insert_general(int v) {
    return true;
    //return G.get_deg(v) == 2;
}
 
bool maximize(double &a, double b) {
    if (a < b) {
        a = b;
        return true;
    }
    else return false;
}
 
string my_to_string(int x) {
    if (x == 0) return "0";
    string s = "";
    bool neg = false;
    if (x < 0) {
        neg = true;
        x = -x;
    }
    while (x > 0) {
        s.push_back(char(int('0') + x % 10));
        x /= 10;
    }
    if (neg) s.push_back('-');
    reverse(s.begin(), s.end());
    return s;
}
 
string my_double_to_string(double x) {
    std::ostringstream strs;
    strs << x;
    std::string str = strs.str();
    return str;
}
 
bool equals(double x, double y) {
    return abs(x - y) <= eps;
}
 
namespace tree_match_graph {
    Graph G;
 
    vector<int> match;
    double best_match_score;
    int best_root_map_to, best_color_set, best_n_del_left;
    vector<int> best_coloring;
    vector<vector<vector<vector<double>>>> fm, fi, fd; //f(u, v, color_set_use, num_deletion_left)
    vector<vector<vector<double>>> fm_temp;
    vector<vector<vector<vector<vector<int>>>>> trace_fm_color, trace_fm_n_del_left, trace_fm_nxt_vertex;
    vector<vector<vector<vector<int>>>> trace_fi_nxt_vertex, trace_fd_nxt_vertex;
 
    vector<int> choosed, best_choosed;
    vector<bool> can_use_color_set;
    double pre_assign_score;
 
    //variables stored result
    vector<int> inserted_nodes;
    vector<int> map_to; //map_to[q] = v => q is map to v; map_to[q] = -1 => q is deleted node
 
    double get_similar_score(int q, int v) {
        return similar_score[graph_to_tree::origin[q]][v];
    }
 
    bool can_map(int color_set_use, int v) {
        if (!can_use_color_set[color_set_use]) return false;
        if (choosed[v] != -1) return true;
        return (get_bit(color_set_use, color[v]) == 1);
    }
 
    bool can_map(int u, int color_set_use, int v) {
        int ou = graph_to_tree::origin[u];
        if (match[ou] == -1)
            return (can_map(color_set_use, v) && homologous(ou, v));
        else return (match[ou] == v);
    }
 
    bool can_delete(int q) {
        int oq = graph_to_tree::origin[q];
        if (match[oq] != -1) return false;
        return (Q_graph.get_deg(oq) == 2);
    }
 
    bool can_insert(int v) {
        return ((G.get_deg(v) == 2) && (choosed[v] == -1));
    }
 
    int add_vertex(int color_set, int vertex) {
        return (choosed[vertex] == -1) ? (color_set + (1 << color[vertex])) : color_set;
    }
 
    int remove_vertex(int color_set, int vertex) {
        return (choosed[vertex] == -1) ? (color_set - (1 << color[vertex])) : color_set;
    }
 
    void update_fm(int q, int v, int color_set_prev, int n_del_left_prev, int k_th_child, int color_set_on_child, int n_del_left_on_child) {
        if (!can_use_color_set[color_set_prev] || !can_use_color_set[color_set_on_child]) return;
        if (equals(fm[q][v][color_set_prev][n_del_left_prev], -INF)) return;
 
        if (MODE == DEBUG_MODE) write_log("update_fm(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_prev = "
                                          + my_to_string(color_set_prev) + ", n_del_left_prev = " + my_to_string(n_del_left_prev)
                                          + ", k_th_child = " + my_to_string(k_th_child) + ", color_set_on_child = "
                                          + my_to_string(color_set_on_child) + ", n_del_left_on_child = " + my_to_string(n_del_left_on_child) + ")...\n");
        int color_set_use = color_set_prev | color_set_on_child;
        int n_del_left = n_del_left_prev + n_del_left_on_child;
        int child = Q_tree.child[q][k_th_child];
        for(pair<int, double> &neighbor : G.adj[v]) {
            int u = neighbor.first; double w = neighbor.second;
            if (can_map(child, color_set_on_child, u)) {
                //map child -> u
                if (!equals(fm[child][u][color_set_on_child][n_del_left_on_child], -INF))
                    if (maximize(fm_temp[v][color_set_use][n_del_left], fm[q][v][color_set_prev][n_del_left_prev]
                                                                    + fm[child][u][color_set_on_child][n_del_left_on_child] + w))
                    {
                        trace_fm_color[q][k_th_child][v][color_set_use][n_del_left] = color_set_on_child;
                        trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left] = n_del_left_on_child;
                        trace_fm_nxt_vertex[q][k_th_child][v][color_set_use][n_del_left] = u;
                    };
                //insert child
                if (can_insert(u) && (!equals(fi[child][u][color_set_on_child][n_del_left_on_child], -INF))) {
                    if (maximize(fm_temp[v][color_set_use][n_del_left], fm[q][v][color_set_prev][n_del_left_prev]
                                                                    + fi[child][u][color_set_on_child][n_del_left_on_child] + w))
                    {
                        trace_fm_color[q][k_th_child][v][color_set_use][n_del_left] = color_set_on_child;
                        trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left] = n_del_left_on_child;
                        trace_fm_nxt_vertex[q][k_th_child][v][color_set_use][n_del_left] = - u - 1;
                    };
                }
            }
        }
        if (can_delete(child) && (!equals(fd[child][v][color_set_on_child][n_del_left_on_child], -INF))) {
            //delete child
            if (maximize(fm_temp[v][color_set_use][n_del_left], fm[q][v][color_set_prev][n_del_left_prev]
                                                            + fd[child][v][color_set_on_child][n_del_left_on_child]))
            {
                trace_fm_color[q][k_th_child][v][color_set_use][n_del_left] = color_set_on_child;
                trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left] = n_del_left_on_child;
                trace_fm_nxt_vertex[q][k_th_child][v][color_set_use][n_del_left] = v; //keep
            };
        }
        if (MODE == DEBUG_MODE) write_log("update_fm(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_prev = "
                                          + my_to_string(color_set_prev) + ", n_del_left_prev = " + my_to_string(n_del_left_prev)
                                          + ", k_th_child = " + my_to_string(k_th_child) + ", color_set_on_child = "
                                          + my_to_string(color_set_on_child) + ", n_del_left_on_child = " + my_to_string(n_del_left_on_child) + ") done\n");
    }
 
    void update_fm(int q, int k_th_child) {
        if (MODE == DEBUG_MODE) write_log("update_fm(q = " + my_to_string(q) + ", k_th_child = " + my_to_string(k_th_child) + ")....\n");
        for(int v = 0; v < G.n; ++v)
            for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
                for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left)
                    fm_temp[v][color_set][n_del_left] = -INF;
 
        for(int color_set_prev = (1 << n_colors) - 1; color_set_prev >= 0; --color_set_prev)
            if (can_use_color_set[color_set_prev])
                for(int n_del_left_prev = 0; n_del_left_prev <= n_del; ++n_del_left_prev) {
                    for(int color_set_on_child = 0; color_set_on_child < (1 << n_colors); ++color_set_on_child)
                        if ((can_use_color_set[color_set_on_child]) &&((color_set_prev + color_set_on_child) == (color_set_prev | color_set_on_child)))
                            for(int n_del_left_on_child = 0; n_del_left_on_child <= n_del - n_del_left_prev; ++n_del_left_on_child)
                                for(int v = 0; v < G.n; ++v) {
                                    if (can_map(q, color_set_prev, v))
                                        update_fm(q, v, color_set_prev, n_del_left_prev, k_th_child, color_set_on_child, n_del_left_on_child);
                                }
                }
 
        for(int v = 0; v < G.n; ++v)
            for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
                for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left)
                    fm[q][v][color_set][n_del_left] = fm_temp[v][color_set][n_del_left];
 
        if (MODE == DEBUG_MODE) write_log("update_fm(q = " + my_to_string(q) + ", k_th_child = " + my_to_string(k_th_child) + ") done\n");
    }
 
    // color[v] belongs to color_set_use
    void update_fi(int q, int v, int color_set_use, int n_del_left) {
        if (!can_use_color_set[color_set_use]) return;
        if (MODE == DEBUG_MODE) write_log("update_fi(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
                                          + my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
        int new_color_set = color_set_use - (1 << color[v]);
        for(pair<int, double> &neighbor : G.adj[v]) {
            int u = neighbor.first; double w = neighbor.second;
            if (can_map(new_color_set, u)) {
                if (can_map(q, new_color_set, u) && (!equals(fm[q][u][new_color_set][n_del_left], -INF)))
                    if (maximize(fi[q][v][color_set_use][n_del_left], per_ins + fm[q][u][new_color_set][n_del_left] + w)) {
                        trace_fi_nxt_vertex[q][v][color_set_use][n_del_left] = u;
                    };
                if (can_insert(u) && (!equals(fi[q][u][new_color_set][n_del_left], -INF))) {
                    maximize(fi[q][v][color_set_use][n_del_left], per_ins + fi[q][u][new_color_set][n_del_left] + w);
                    trace_fi_nxt_vertex[q][v][color_set_use][n_del_left] = - u - 1;
                }
            }
        }
        if (MODE == DEBUG_MODE) write_log("update_fi(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
                                          + my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
    }
 
    void update_fi(int q) {
        if (MODE == DEBUG_MODE) write_log("update_fi(q = " + my_to_string(q) + ")....\n");
        for(int v = 0; v < G.n; ++v)
            if (can_insert(v))
                for(int color_set_use = 0; color_set_use < (1 << n_colors); ++color_set_use)
                    if (can_use_color_set[color_set_use])
                        for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left)
                            if (can_map(color_set_use, v))
                                update_fi(q, v, color_set_use, n_del_left);
        if (MODE == DEBUG_MODE) write_log("update_fi(q = " + my_to_string(q) + ") done\n");
    }
 
    void update_fd(int q, int v, int color_set_use, int n_del_left) {
        if (!can_use_color_set[color_set_use]) return;
        if (n_del_left < 1) return;
        if (MODE == DEBUG_MODE) write_log("update_fd(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = " + my_to_string(color_set_use)
                                    + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
        int q_nxt = Q_tree.child[q][0];
        for(pair<int, double> &neighbor : G.adj[v]) {
            int u = neighbor.first; double w = neighbor.second;
            if (can_map(color_set_use, u)) {
                if (can_map(q_nxt, color_set_use, u) && (!equals(fm[q_nxt][u][color_set_use][n_del_left - 1], -INF))) {
                    if (maximize(fd[q][v][color_set_use][n_del_left], per_del + fm[q_nxt][u][color_set_use][n_del_left - 1] + w)) {
                        trace_fd_nxt_vertex[q][v][color_set_use][n_del_left] = u;
                    };
                }
                if (!equals(fi[q_nxt][u][color_set_use][n_del_left - 1], -INF)) {
                    if (maximize(fd[q][v][color_set_use][n_del_left], per_del + fi[q_nxt][u][color_set_use][n_del_left - 1] + w)) {
                        trace_fd_nxt_vertex[q][v][color_set_use][n_del_left] = - u - 1;
                    };
                }
            }
        }
        if (can_delete(q_nxt) && (n_del_left > 0) && (!equals(fd[q_nxt][v][color_set_use][n_del_left - 1], -INF))) {
            if (maximize(fd[q][v][color_set_use][n_del_left], per_del + fd[q_nxt][v][color_set_use][n_del_left - 1])) {
                        }
                trace_fd_nxt_vertex[q][v][color_set_use][n_del_left] = v;
            };
        }
        if (MODE == DEBUG_MODE) write_log("update_fd(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = " + my_to_string(color_set_use)
                                    + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
    }
 
    void update_fd(int q) {
        if (!can_delete(q)) return;
        if (MODE == DEBUG_MODE) write_log("update_fd(q = " + my_to_string(q) + ")....\n");
        for(int v = 0; v < G.n; ++v)
            for(int color_set_use = 0; color_set_use < (1 << n_colors); ++color_set_use)
                if (can_use_color_set[color_set_use])
                    for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left)
                        update_fd(q, v, color_set_use, n_del_left);
        if (MODE == DEBUG_MODE) write_log("update_fd(q = " + my_to_string(q) + ") done\n");
    }
 
    void init_dp(int q) {
        if (MODE == DEBUG_MODE) write_log("init_dp(q = " + my_to_string(q) + ")...\n");
 
        for(int v = 0; v < G.n; ++v)
            for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
                for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
                    fm[q][v][color_set][n_del_left] = -INF;
                    fi[q][v][color_set][n_del_left] = -INF;
                    fd[q][v][color_set][n_del_left] = -INF;
                }
        for(int v = 0; v < G.n; ++v)
            if (can_map(q, (1 << color[v]), v)) {
                fm[q][v][add_vertex(0, v)][0] = (match[q] == -1) ? get_similar_score(q, v) : 0.0;
            }
 
        if (MODE == DEBUG_MODE) write_log("init_dp(q = " + my_to_string(q) + ") done\n");
    }
 
    void write_log_dp_values(int q) {
        write_log("get dp values at node " + my_to_string(q) + "...\n");
        write_log("get fm(q = " + my_to_string(q) + ")\n");
        for(int v = 0; v < G.n; ++v)
            for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
                for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
                    if (!equals(fm[q][v][color_set][n_del_left], -INF))
                        write_log("fm(" + my_to_string(q) + "," + my_to_string(v) + "," + my_to_string(color_set) + "," + my_to_string(n_del_left) + ") = " + my_double_to_string(fm[q][v][color_set][n_del_left]) + "\n");
                }
        write_log("get fi(q = " + my_to_string(q) + ")\n");
        for(int v = 0; v < G.n; ++v)
            for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
                for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
                    if (!equals(fi[q][v][color_set][n_del_left], -INF))
                        write_log("fi(" + my_to_string(q) + "," + my_to_string(v) + "," + my_to_string(color_set) + "," + my_to_string(n_del_left) + ") = " + my_double_to_string(fi[q][v][color_set][n_del_left]) + "\n");
                }
        write_log("get fd(q = " + my_to_string(q) + ")\n");
        for(int v = 0; v < G.n; ++v)
            for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
                for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
                    if (!equals(fd[q][v][color_set][n_del_left], -INF))
                        write_log("fd(" + my_to_string(q) + "," + my_to_string(v) + "," + my_to_string(color_set) + "," + my_to_string(n_del_left) + ") = " + my_double_to_string(fd[q][v][color_set][n_del_left]) + "\n");
                }
        write_log("get dp values at node " + my_to_string(q) + " done\n");
    }
 
    void DFS(int u) {
        if (MODE == DEBUG_MODE) write_log("DFS have just enter node " + my_to_string(u) + "\n");
        init_dp(u);
        for(int k = 0; k < Q_tree.child[u].size(); ++k) {
            if (MODE == DEBUG_MODE) write_log("start DFS child " + my_to_string(Q_tree.child[u][k]) + " of " + my_to_string(u) + "\n");
            DFS(Q_tree.child[u][k]);
            update_fm(u, k);
        }
        update_fi(u);
        update_fd(u);
        if (MODE == DEBUG_MODE) write_log("DFS subtree rooted at " + my_to_string(u) + " done\n");
 
        if (MODE == DEBUG_MODE) write_log_dp_values(u);
    }
 
    //forward declaration
    void trace_result_matching_fm(int q, int v, int color_set_use, int n_del_left);
    void trace_result_matching_fi(int q, int v, int color_set_use, int n_del_left);
    void trace_result_matching_fd(int q, int v, int color_set_use, int n_del_left);
 
    void trace_result_matching_fm(int q, int v, int color_set_use, int n_del_left) {
        if (MODE == DEBUG_MODE) write_log("trace_result_matching_fm(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
                                          + my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
        if (MODE == DEBUG_MODE) write_log("with fm = " + my_double_to_string(fm[q][v][color_set_use][n_del_left]));
        if (MODE == DEBUG_MODE) write_log("cost match mode " + my_to_string(q) + "->"
                                          + my_to_string(v) + " = " + my_double_to_string(get_similar_score(q, v)) + "\n");
        map_to[q] = v;
        for(int k_th_child = (int)(Q_tree.child[q].size()) - 1; k_th_child >= 0; --k_th_child) {
            int child = Q_tree.child[q][k_th_child];
            int u = trace_fm_nxt_vertex[q][k_th_child][v][color_set_use][n_del_left];
            if (MODE == DEBUG_MODE) write_log("k_th_child = " + my_to_string(k_th_child)
                                              + ", child = " + my_to_string(child) + ", u = " + my_to_string(u) + "\n");
            if (u == v) {
                trace_result_matching_fd(child, v, trace_fm_color[q][k_th_child][v][color_set_use][n_del_left],
                                         trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left]);
            }
            else if (u >= 0) {
                if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(u)
                                                  + "=" + my_double_to_string(G.get_weight(v, u)));
                trace_result_matching_fm(child, u, trace_fm_color[q][k_th_child][v][color_set_use][n_del_left],
                                         trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left]);
            }
            else { // u < 0
                if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(-u-1)
                                                  + "=" + my_double_to_string(G.get_weight(v, -u-1)));
                trace_result_matching_fi(child, -u - 1, trace_fm_color[q][k_th_child][v][color_set_use][n_del_left],
                                         trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left]);
            }
            int nxt_color_set = color_set_use - trace_fm_color[q][k_th_child][v][color_set_use][n_del_left];
            int nxt_n_del_left = n_del_left - trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left];
            color_set_use = nxt_color_set;
            n_del_left = nxt_n_del_left;
        }
 
        if (MODE == DEBUG_MODE) write_log("trace_result_matching_fm(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
                                          + my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
    }
 
    void trace_result_matching_fi(int q, int v, int color_set_use, int n_del_left) {
        if (MODE == DEBUG_MODE) write_log("trace_result_matching_fi(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
                                          + my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
        if (MODE == DEBUG_MODE) write_log("with fi = " + my_double_to_string(fi[q][v][color_set_use][n_del_left]));
        inserted_nodes.push_back(v);
        int u = trace_fi_nxt_vertex[q][v][color_set_use][n_del_left];
        if (MODE == DEBUG_MODE) write_log("u = " + my_to_string(u) + "\n");
        if (u >= 0) {
            if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(u)
                                              + "=" + my_double_to_string(G.get_weight(v, u)));
            trace_result_matching_fm(q, u, color_set_use - (1 << color[v]), n_del_left);
        }
        else { //u < 0
            if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(-u-1)
                                              + "=" + my_double_to_string(G.get_weight(v, -u-1)));
            trace_result_matching_fi(q, -u - 1, color_set_use - (1 << color[v]), n_del_left);
        }
        if (MODE == DEBUG_MODE) write_log("trace_result_matching_fi(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
                                          + my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
    }
 
    void trace_result_matching_fd(int q, int v, int color_set_use, int n_del_left) {
        if (MODE == DEBUG_MODE) write_log("trace_result_matching_fd(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
                                          + my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
        if (MODE == DEBUG_MODE) write_log("with fd = " + my_double_to_string(fd[q][v][color_set_use][n_del_left]));
        int u = trace_fd_nxt_vertex[q][v][color_set_use][n_del_left];
        if (MODE == DEBUG_MODE) write_log("u = " + my_to_string(u) + "\n");
        int q_nxt = Q_tree.child[q][0];
        if (u == v) {
            trace_result_matching_fd(q_nxt, v, color_set_use, n_del_left - 1);
        }
        else if (u >= 0) {
            if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(u)
                                              + "=" + my_double_to_string(G.get_weight(v, u)));
            trace_result_matching_fm(q_nxt, u, color_set_use, n_del_left - 1);
        }
        else { // u < 0
            if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(-u-1)
                                              + "=" + my_double_to_string(G.get_weight(v, -u-1)));
            trace_result_matching_fi(q_nxt, -u - 1, color_set_use, n_del_left - 1);
        }
        if (MODE == DEBUG_MODE) write_log("trace_result_matching_fd(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
                                          + my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
    }
 
    void get_result() {
        if (MODE == DEBUG_MODE) write_log("get_result()...\n");
        double this_best_score = -INF;
        int root_map_to = -1, start_color_set = -1, start_n_del_left = -1;
        for(int v = 0; v < G.n; ++v)
            //map Q.root -> v
            for(int color_set_use = 0; color_set_use < (1 << n_colors); ++color_set_use)
                for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
                    if ((MODE == DEBUG_MODE) && (!equals(fm[Q_tree.root][v][color_set_use][n_del_left], -INF)))
                        write_log("fm(" + my_to_string(Q_tree.root) + "," + my_to_string(v) + "," + my_to_string(color_set_use) + "," + my_to_string(n_del_left) + ") = " + my_double_to_string(fm[Q_tree.root][v][color_set_use][n_del_left]) + "\n");
                    if (maximize(this_best_score, fm[Q_tree.root][v][color_set_use][n_del_left])) {
                        root_map_to = v;
                        start_color_set = color_set_use;
                        start_n_del_left = n_del_left;
                    };
                }
        if (!equals(this_best_score, -INF)) this_best_score += pre_assign_score;
 
        if (maximize(best_match_score, this_best_score)) {
                best_root_map_to = root_map_to;
                best_color_set = start_color_set;
                best_n_del_left = start_n_del_left;
                for(int v = 0; v < G.n; ++v) {
                    best_coloring[v] = color[v];
                    best_choosed[v] = choosed[v];
                }
        };
        //cout << "this_best_score = " << this_best_score << endl;
        if (MODE == DEBUG_MODE) write_log("this_best_score = " + my_double_to_string(this_best_score) + "\n");
        if (MODE == DEBUG_MODE) write_log("best_match_score = " + my_double_to_string(best_match_score) + "\n");
        if (MODE == DEBUG_MODE) write_log("get_result() done\n");
    }
 
    void random_coloring() {
        if (MODE == DEBUG_MODE) write_log("start random coloring...\n");
        for(int v = 0; v < G.n; ++v) {
            color[v] =  v % n_colors; //rnd.next(0, n_colors - 1); //rand() % n_colors;
            if (MODE == DEBUG_MODE) write_log("color(" + my_to_string(v) + ") = " + my_to_string(color[v]) + "\n");
        }
        if (MODE == DEBUG_MODE) write_log("random coloring done\n");
    }
 
    void init_before_dp_on_tree() {
        can_use_color_set.resize((1 << n_colors));
        for(int color_set = 0; color_set < (1 << n_colors); ++color_set) {
            bool ok = true;
            for(int v = 0; v < G.n; ++v)
                if (choosed[v] != -1)
                    if (get_bit(color_set, color[v]) == 1)
                        ok = false;
            can_use_color_set[color_set] = ok;
        }
        pre_assign_score = 0.0;
        for(int q = 0; q < Q_graph.n; ++q)
            if (match[q] != -1)
                pre_assign_score += get_similar_score(q, match[q]);
        cout << "pre_assign_score = " << pre_assign_score << endl;
    }
 
    void dp_on_tree() {
 
        for(int i = 0; i < G.n; ++i) cout << "color(" << i << ") = " << color[i] << endl;
        for(int i = 0; i < Q_graph.n; ++i)
            if (match[i] != -1) cout << i << "->" << match[i] << endl;
 
        init_before_dp_on_tree();
        if (MODE == DEBUG_MODE) write_log("start DFS from Q_tree.root = " + my_to_string(Q_tree.root) + "\n");
        DFS(Q_tree.root);
        if (MODE == DEBUG_MODE) write_log("DFS done\n");
        get_result();
        cout << "1 phase dp done\n";
    }
 
    void backtrack_assign(int qi, int set_choosed) {
        if (qi >= graph_to_tree::dup_ver.size()) {
            dp_on_tree();
            return;
        }
 
        int q = graph_to_tree::dup_ver[qi];
        for(int v = 0; v < G.n; ++v)
            if ((choosed[v] == -1) && (get_bit(set_choosed, color[v]) == 0) && (G.get_deg(v) >= Q_graph.get_deg(qi) - n_del)) {
                choosed[v] = q;
                match[q] = v;
                backtrack_assign(qi + 1, set_choosed + (1 << color[v]));
                choosed[v] = -1;
                match[q] = -1;
            }
    }
 
    void pre_assignment() {
        choosed.resize(G.n); best_choosed.resize(G.n);
        for(int v = 0; v < G.n; ++v) choosed[v] = -1;
        match.resize(Q_graph.n);
        for(int q = 0; q < match.size(); ++q) match[q] = -1;
        //backtrack_assign(0, 0);
        match[1] = 2; choosed[2] = 1; dp_on_tree();
    }
 
    void run() {
        random_coloring();
        cout << "random coloring done\n";
        pre_assignment();
    }
 
    void init_trace_best_matching() {
        for(int v = 0; v < G.n; ++v) color[v] = best_coloring[v];
        choosed = best_choosed;
        for(int q = 0; q < Q_graph.n; ++q)
            match[q] = -1;
        for(int v = 0; v < G.n; ++v)
            if (choosed[v] != -1)
                match[choosed[v]] = v;
        init_before_dp_on_tree();
        DFS(Q_tree.root);
    }
 
    void trace_best_matching() {
        inserted_nodes.resize(0);
        map_to = vector<int>(Q_tree.n, -1);
        if (MODE == DEBUG_MODE) write_log("start trace best matching...\n");
        if (equals(best_match_score, -INF)) {
            cout << "No matching found!\n";
            write_log("No matching found!\n");
            if (MODE == DEBUG_MODE) write_log("No matching found!\ntrace best matching done\n");
            return;
        }
 
        write_log("best_match_score(in a connected component) = " + my_to_string(best_match_score) + "\n");
        cout << "trace result with best_match_score = " << best_match_score << endl;
 
        init_trace_best_matching();
 
        trace_result_matching_fm(Q_tree.root, best_root_map_to, best_color_set, best_n_del_left);
        if (MODE == DEBUG_MODE) write_log("trace best matching done\n");
        write_log("map_to = {");
        for(int q = 0; q < Q_tree.n; ++q) write_log(my_to_string(map_to[q]) + ",");
        write_log("}\n");
        write_log("inserted_nodes = {");
        for(int v : inserted_nodes) write_log(my_to_string(v) + ",");
        write_log("}\n");
    }
 
    void init_vector(vector<vector<vector<double>>> &v, int dim1, int dim2, int dim3, double val) {
        assert(min(dim1, min(dim2, dim3)) >= 0);
        v.resize(dim1);
        for(int i = 0; i < dim1; ++i) {
            v[i].resize(dim2);
            for(int j = 0; j < dim2; ++j) {
                v[i][j].resize(dim3);
                for(int k = 0; k < dim3; ++k) {
                    v[i][j][k] = val;
                }
            }
        }
    }
 
    void init_vector(vector<vector<vector<vector<double>>>> &v, int dim1, int dim2, int dim3, int dim4, double val) {
        assert(min(dim1, min(dim2, min(dim3, dim4))) >= 0);
        cout << "4 dims = " << dim1 << " " << dim2 << " " << dim3 << " " << dim4 << " " << dim1 * dim2 * dim3 * dim4 << endl;
        v.resize(dim1);
        for(int i = 0; i < dim1; ++i) {
            v[i].resize(dim2);
            for(int j = 0; j < dim2; ++j) {
                v[i][j].resize(dim3);
                for(int k = 0; k < dim3; ++k) {
                    v[i][j][k].resize(dim4);
                    for(int t = 0; t < dim4; ++t)
                        v[i][j][k][t] = val;
                }
            }
        }
    }
 
    void init_vector(vector<vector<vector<vector<int>>>> &v, int dim1, int dim2, int dim3, int dim4, int val) {
        assert(min(dim1, min(dim2, min(dim3, dim4))) >= 0);
        v.resize(dim1);
        for(int i = 0; i < dim1; ++i) {
            v[i].resize(dim2);
            for(int j = 0; j < dim2; ++j) {
                v[i][j].resize(dim3);
                for(int k = 0; k < dim3; ++k) {
                    v[i][j][k].resize(dim4);
                    for(int t = 0; t < dim4; ++t)
                        v[i][j][k][t] = val;
                }
            }
        }
    }
 
    void init_vector(vector<vector<vector<vector<vector<int>>>>> &v, int dim1, int dim2, int dim3, int dim4, int dim5, double val) {
        assert(min(dim1, min(dim2, min(dim3, min(dim4, dim5)))) >= 0);
        v.resize(dim1);
        for(int i = 0; i < dim1; ++i) {
            v[i].resize(dim2);
            for(int j = 0; j < dim2; ++j) {
                v[i][j].resize(dim3);
                for(int k = 0; k < dim3; ++k) {
                    v[i][j][k].resize(dim4);
                    for(int t = 0; t < dim4; ++t) {
                        v[i][j][k][t].resize(dim5);
                        for(int u = 0; u < dim5; ++u)
                            v[i][j][k][t][u] = val;
                    }
                }
            }
        }
    }
 
 
    void init_vector_dimension() {
        init_vector(fm, Q_tree.n, G.n, (1 << n_colors), n_del + 1, -INF);
        init_vector(fi, Q_tree.n, G.n, (1 << n_colors), n_del + 1, -INF);
        init_vector(fd, Q_tree.n, G.n, (1 << n_colors), n_del + 1, -INF);
 
        init_vector(fm_temp, G.n, (1 << n_colors), n_del + 1, -INF);
 
        trace_fm_color.resize(Q_tree.n);
        trace_fm_n_del_left.resize(Q_tree.n);
        trace_fm_nxt_vertex.resize(Q_tree.n);
 
        init_vector(trace_fi_nxt_vertex, Q_tree.n, G.n, (1 << n_colors), n_del + 1, -1);
        init_vector(trace_fd_nxt_vertex, Q_tree.n, G.n, (1 << n_colors), n_del + 1, -1);
 
        for(int u = 0; u < Q_tree.n; ++u) {
            init_vector(trace_fm_color[u], Q_tree.get_num_child(u), G.n, (1 << n_colors), n_del + 1, -1);
            init_vector(trace_fm_n_del_left[u], Q_tree.get_num_child(u), G.n, (1 << n_colors), n_del + 1, -1);
            init_vector(trace_fm_nxt_vertex[u], Q_tree.get_num_child(u), G.n, (1 << n_colors), n_del + 1, -1);
        }
    }
 
    void solve() {
        cout << "enter solve()\n";
        init_vector_dimension();
        cout << "init dim done\n";
        int n_loops = 1;
        best_match_score = -INF;
        best_coloring.resize(G.n);
        cout << "while loop\n";
        while (n_loops > 0) {
            n_loops--;
            if (MODE == DEBUG_MODE) write_log("n_loops = " + my_to_string(n_loops));
            run();
            if (MODE == DEBUG_MODE) write_log("run() done\n");
        }
        trace_best_matching();
    }
 
    void set_graph(Graph &g) {
        G = g;
    }
}
 
namespace tree_match_graph {
    Graph G;
 
    vector<int> match;
    double best_match_score;
    int best_root_map_to, best_color_set, best_n_del_left;
    vector<int> best_coloring;
    vector<vector<vector<vector<double>>>> fm, fi, fd; //f(u, v, color_set_use, num_deletion_left)
    vector<vector<vector<double>>> fm_temp;
    vector<vector<vector<vector<vector<int>>>>> trace_fm_color, trace_fm_n_del_left, trace_fm_nxt_vertex;
    vector<vector<vector<vector<int>>>> trace_fi_nxt_vertex, trace_fd_nxt_vertex;
 
    vector<int> choosed, best_choosed;
    vector<bool> can_use_color_set;
    double pre_assign_score;
 
    //variables stored result
    vector<int> inserted_nodes;
    vector<int> map_to; //map_to[q] = v => q is map to v; map_to[q] = -1 => q is deleted node
 
    double get_similar_score(int q, int v) {
        return similar_score[graph_to_tree::origin[q]][v];
    }
 
    bool can_map(int color_set_use, int v) {
        if (!can_use_color_set[color_set_use]) return false;
        if (choosed[v] != -1) return true;
        return (get_bit(color_set_use, color[v]) == 1);
    }
 
    bool can_map(int u, int color_set_use, int v) {
        int ou = graph_to_tree::origin[u];
        if (match[ou] == -1)
            return (can_map(color_set_use, v) && homologous(ou, v));
        else return (match[ou] == v);
    }
 
    bool can_delete(int q) {
        int oq = graph_to_tree::origin[q];
        if (match[oq] != -1) return false;
        return (Q_graph.get_deg(oq) == 2);
    }
 
    bool can_insert(int v) {
        return ((G.get_deg(v) == 2) && (choosed[v] == -1));
    }
 
    int add_vertex(int color_set, int vertex) {
        return (choosed[vertex] == -1) ? (color_set + (1 << color[vertex])) : color_set;
    }
 
    int remove_vertex(int color_set, int vertex) {
        return (choosed[vertex] == -1) ? (color_set - (1 << color[vertex])) : color_set;
    }
 
    void update_fm(int q, int v, int color_set_prev, int n_del_left_prev, int k_th_child, int color_set_on_child, int n_del_left_on_child) {
        if (!can_use_color_set[color_set_prev] || !can_use_color_set[color_set_on_child]) return;
        if (equals(fm[q][v][color_set_prev][n_del_left_prev], -INF)) return;
 
        if (MODE == DEBUG_MODE) write_log("update_fm(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_prev = "
                                          + my_to_string(color_set_prev) + ", n_del_left_prev = " + my_to_string(n_del_left_prev)
                                          + ", k_th_child = " + my_to_string(k_th_child) + ", color_set_on_child = "
                                          + my_to_string(color_set_on_child) + ", n_del_left_on_child = " + my_to_string(n_del_left_on_child) + ")...\n");
        int color_set_use = color_set_prev | color_set_on_child;
        int n_del_left = n_del_left_prev + n_del_left_on_child;
        int child = Q_tree.child[q][k_th_child];
        for(pair<int, double> &neighbor : G.adj[v]) {
            int u = neighbor.first; double w = neighbor.second;
            if (can_map(child, color_set_on_child, u)) {
                //map child -> u
                if (!equals(fm[child][u][color_set_on_child][n_del_left_on_child], -INF))
                    if (maximize(fm_temp[v][color_set_use][n_del_left], fm[q][v][color_set_prev][n_del_left_prev]
                                                                    + fm[child][u][color_set_on_child][n_del_left_on_child] + w))
                    {
                        trace_fm_color[q][k_th_child][v][color_set_use][n_del_left] = color_set_on_child;
                        trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left] = n_del_left_on_child;
                        trace_fm_nxt_vertex[q][k_th_child][v][color_set_use][n_del_left] = u;
                    };
                //insert child
                if (can_insert(u) && (!equals(fi[child][u][color_set_on_child][n_del_left_on_child], -INF))) {
                    if (maximize(fm_temp[v][color_set_use][n_del_left], fm[q][v][color_set_prev][n_del_left_prev]
                                                                    + fi[child][u][color_set_on_child][n_del_left_on_child] + w))
                    {
                        trace_fm_color[q][k_th_child][v][color_set_use][n_del_left] = color_set_on_child;
                        trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left] = n_del_left_on_child;
                        trace_fm_nxt_vertex[q][k_th_child][v][color_set_use][n_del_left] = - u - 1;
                    };
                }
            }
        }
        if (can_delete(child) && (!equals(fd[child][v][color_set_on_child][n_del_left_on_child], -INF))) {
            //delete child
            if (maximize(fm_temp[v][color_set_use][n_del_left], fm[q][v][color_set_prev][n_del_left_prev]
                                                            + fd[child][v][color_set_on_child][n_del_left_on_child]))
            {
                trace_fm_color[q][k_th_child][v][color_set_use][n_del_left] = color_set_on_child;
                trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left] = n_del_left_on_child;
                trace_fm_nxt_vertex[q][k_th_child][v][color_set_use][n_del_left] = v; //keep
            };
        }
        if (MODE == DEBUG_MODE) write_log("update_fm(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_prev = "
                                          + my_to_string(color_set_prev) + ", n_del_left_prev = " + my_to_string(n_del_left_prev)
                                          + ", k_th_child = " + my_to_string(k_th_child) + ", color_set_on_child = "
                                          + my_to_string(color_set_on_child) + ", n_del_left_on_child = " + my_to_string(n_del_left_on_child) + ") done\n");
    }
 
    void update_fm(int q, int k_th_child) {
        if (MODE == DEBUG_MODE) write_log("update_fm(q = " + my_to_string(q) + ", k_th_child = " + my_to_string(k_th_child) + ")....\n");
        for(int v = 0; v < G.n; ++v)
            for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
                for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left)
                    fm_temp[v][color_set][n_del_left] = -INF;
 
        for(int color_set_prev = (1 << n_colors) - 1; color_set_prev >= 0; --color_set_prev)
            if (can_use_color_set[color_set_prev])
                for(int n_del_left_prev = 0; n_del_left_prev <= n_del; ++n_del_left_prev) {
                    for(int color_set_on_child = 0; color_set_on_child < (1 << n_colors); ++color_set_on_child)
                        if ((can_use_color_set[color_set_on_child]) &&((color_set_prev + color_set_on_child) == (color_set_prev | color_set_on_child)))
                            for(int n_del_left_on_child = 0; n_del_left_on_child <= n_del - n_del_left_prev; ++n_del_left_on_child)
                                for(int v = 0; v < G.n; ++v) {
                                    if (can_map(q, color_set_prev, v))
                                        update_fm(q, v, color_set_prev, n_del_left_prev, k_th_child, color_set_on_child, n_del_left_on_child);
                                }
                }
 
        for(int v = 0; v < G.n; ++v)
            for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
                for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left)
                    fm[q][v][color_set][n_del_left] = fm_temp[v][color_set][n_del_left];
 
        if (MODE == DEBUG_MODE) write_log("update_fm(q = " + my_to_string(q) + ", k_th_child = " + my_to_string(k_th_child) + ") done\n");
    }
 
    // color[v] belongs to color_set_use
    void update_fi(int q, int v, int color_set_use, int n_del_left) {
        if (!can_use_color_set[color_set_use]) return;
        if (MODE == DEBUG_MODE) write_log("update_fi(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
                                          + my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
        int new_color_set = color_set_use - (1 << color[v]);
        for(pair<int, double> &neighbor : G.adj[v]) {
            int u = neighbor.first; double w = neighbor.second;
            if (can_map(new_color_set, u)) {
                if (can_map(q, new_color_set, u) && (!equals(fm[q][u][new_color_set][n_del_left], -INF)))
                    if (maximize(fi[q][v][color_set_use][n_del_left], per_ins + fm[q][u][new_color_set][n_del_left] + w)) {
                        trace_fi_nxt_vertex[q][v][color_set_use][n_del_left] = u;
                    };
                if (can_insert(u) && (!equals(fi[q][u][new_color_set][n_del_left], -INF))) {
                    maximize(fi[q][v][color_set_use][n_del_left], per_ins + fi[q][u][new_color_set][n_del_left] + w);
                    trace_fi_nxt_vertex[q][v][color_set_use][n_del_left] = - u - 1;
                }
            }
        }
        if (MODE == DEBUG_MODE) write_log("update_fi(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
                                          + my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
    }
 
    void update_fi(int q) {
        if (MODE == DEBUG_MODE) write_log("update_fi(q = " + my_to_string(q) + ")....\n");
        for(int v = 0; v < G.n; ++v)
            if (can_insert(v))
                for(int color_set_use = 0; color_set_use < (1 << n_colors); ++color_set_use)
                    if (can_use_color_set[color_set_use])
                        for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left)
                            if (can_map(color_set_use, v))
                                update_fi(q, v, color_set_use, n_del_left);
        if (MODE == DEBUG_MODE) write_log("update_fi(q = " + my_to_string(q) + ") done\n");
    }
 
    void update_fd(int q, int v, int color_set_use, int n_del_left) {
        if (!can_use_color_set[color_set_use]) return;
        if (n_del_left < 1) return;
        if (MODE == DEBUG_MODE) write_log("update_fd(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = " + my_to_string(color_set_use)
                                    + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
        int q_nxt = Q_tree.child[q][0];
        for(pair<int, double> &neighbor : G.adj[v]) {
            int u = neighbor.first; double w = neighbor.second;
            if (can_map(color_set_use, u)) {
                if (can_map(q_nxt, color_set_use, u) && (!equals(fm[q_nxt][u][color_set_use][n_del_left - 1], -INF))) {
                    if (maximize(fd[q][v][color_set_use][n_del_left], per_del + fm[q_nxt][u][color_set_use][n_del_left - 1] + w)) {
                        trace_fd_nxt_vertex[q][v][color_set_use][n_del_left] = u;
                    };
                }
                if (!equals(fi[q_nxt][u][color_set_use][n_del_left - 1], -INF)) {
                    if (maximize(fd[q][v][color_set_use][n_del_left], per_del + fi[q_nxt][u][color_set_use][n_del_left - 1] + w)) {
                        trace_fd_nxt_vertex[q][v][color_set_use][n_del_left] = - u - 1;
                    };
                }
            }
        }
        if (can_delete(q_nxt) && (n_del_left > 0) && (!equals(fd[q_nxt][v][color_set_use][n_del_left - 1], -INF))) {
            if (maximize(fd[q][v][color_set_use][n_del_left], per_del + fd[q_nxt][v][color_set_use][n_del_left - 1])) {
                        }
                trace_fd_nxt_vertex[q][v][color_set_use][n_del_left] = v;
            };
        }
        if (MODE == DEBUG_MODE) write_log("update_fd(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = " + my_to_string(color_set_use)
                                    + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
    }
 
    void update_fd(int q) {
        if (!can_delete(q)) return;
        if (MODE == DEBUG_MODE) write_log("update_fd(q = " + my_to_string(q) + ")....\n");
        for(int v = 0; v < G.n; ++v)
            for(int color_set_use = 0; color_set_use < (1 << n_colors); ++color_set_use)
                if (can_use_color_set[color_set_use])
                    for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left)
                        update_fd(q, v, color_set_use, n_del_left);
        if (MODE == DEBUG_MODE) write_log("update_fd(q = " + my_to_string(q) + ") done\n");
    }
 
    void init_dp(int q) {
        if (MODE == DEBUG_MODE) write_log("init_dp(q = " + my_to_string(q) + ")...\n");
 
        for(int v = 0; v < G.n; ++v)
            for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
                for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
                    fm[q][v][color_set][n_del_left] = -INF;
                    fi[q][v][color_set][n_del_left] = -INF;
                    fd[q][v][color_set][n_del_left] = -INF;
                }
        for(int v = 0; v < G.n; ++v)
            if (can_map(q, (1 << color[v]), v)) {
                fm[q][v][add_vertex(0, v)][0] = (match[q] == -1) ? get_similar_score(q, v) : 0.0;
            }
 
        if (MODE == DEBUG_MODE) write_log("init_dp(q = " + my_to_string(q) + ") done\n");
    }
 
    void write_log_dp_values(int q) {
        write_log("get dp values at node " + my_to_string(q) + "...\n");
        write_log("get fm(q = " + my_to_string(q) + ")\n");
        for(int v = 0; v < G.n; ++v)
            for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
                for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
                    if (!equals(fm[q][v][color_set][n_del_left], -INF))
                        write_log("fm(" + my_to_string(q) + "," + my_to_string(v) + "," + my_to_string(color_set) + "," + my_to_string(n_del_left) + ") = " + my_double_to_string(fm[q][v][color_set][n_del_left]) + "\n");
                }
        write_log("get fi(q = " + my_to_string(q) + ")\n");
        for(int v = 0; v < G.n; ++v)
            for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
                for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
                    if (!equals(fi[q][v][color_set][n_del_left], -INF))
                        write_log("fi(" + my_to_string(q) + "," + my_to_string(v) + "," + my_to_string(color_set) + "," + my_to_string(n_del_left) + ") = " + my_double_to_string(fi[q][v][color_set][n_del_left]) + "\n");
                }
        write_log("get fd(q = " + my_to_string(q) + ")\n");
        for(int v = 0; v < G.n; ++v)
            for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
                for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
                    if (!equals(fd[q][v][color_set][n_del_left], -INF))
                        write_log("fd(" + my_to_string(q) + "," + my_to_string(v) + "," + my_to_string(color_set) + "," + my_to_string(n_del_left) + ") = " + my_double_to_string(fd[q][v][color_set][n_del_left]) + "\n");
                }
        write_log("get dp values at node " + my_to_string(q) + " done\n");
    }
 
    void DFS(int u) {
        if (MODE == DEBUG_MODE) write_log("DFS have just enter node " + my_to_string(u) + "\n");
        init_dp(u);
        for(int k = 0; k < Q_tree.child[u].size(); ++k) {
            if (MODE == DEBUG_MODE) write_log("start DFS child " + my_to_string(Q_tree.child[u][k]) + " of " + my_to_string(u) + "\n");
            DFS(Q_tree.child[u][k]);
            update_fm(u, k);
        }
        update_fi(u);
        update_fd(u);
        if (MODE == DEBUG_MODE) write_log("DFS subtree rooted at " + my_to_string(u) + " done\n");
 
        if (MODE == DEBUG_MODE) write_log_dp_values(u);
    }
 
    //forward declaration
    void trace_result_matching_fm(int q, int v, int color_set_use, int n_del_left);
    void trace_result_matching_fi(int q, int v, int color_set_use, int n_del_left);
    void trace_result_matching_fd(int q, int v, int color_set_use, int n_del_left);
 
    void trace_result_matching_fm(int q, int v, int color_set_use, int n_del_left) {
        if (MODE == DEBUG_MODE) write_log("trace_result_matching_fm(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
                                          + my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
        if (MODE == DEBUG_MODE) write_log("with fm = " + my_double_to_string(fm[q][v][color_set_use][n_del_left]));
        if (MODE == DEBUG_MODE) write_log("cost match mode " + my_to_string(q) + "->"
                                          + my_to_string(v) + " = " + my_double_to_string(get_similar_score(q, v)) + "\n");
        map_to[q] = v;
        for(int k_th_child = (int)(Q_tree.child[q].size()) - 1; k_th_child >= 0; --k_th_child) {
            int child = Q_tree.child[q][k_th_child];
            int u = trace_fm_nxt_vertex[q][k_th_child][v][color_set_use][n_del_left];
            if (MODE == DEBUG_MODE) write_log("k_th_child = " + my_to_string(k_th_child)
                                              + ", child = " + my_to_string(child) + ", u = " + my_to_string(u) + "\n");
            if (u == v) {
                trace_result_matching_fd(child, v, trace_fm_color[q][k_th_child][v][color_set_use][n_del_left],
                                         trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left]);
            }
            else if (u >= 0) {
                if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(u)
                                                  + "=" + my_double_to_string(G.get_weight(v, u)));
                trace_result_matching_fm(child, u, trace_fm_color[q][k_th_child][v][color_set_use][n_del_left],
                                         trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left]);
            }
            else { // u < 0
                if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(-u-1)
                                                  + "=" + my_double_to_string(G.get_weight(v, -u-1)));
                trace_result_matching_fi(child, -u - 1, trace_fm_color[q][k_th_child][v][color_set_use][n_del_left],
                                         trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left]);
            }
            int nxt_color_set = color_set_use - trace_fm_color[q][k_th_child][v][color_set_use][n_del_left];
            int nxt_n_del_left = n_del_left - trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left];
            color_set_use = nxt_color_set;
            n_del_left = nxt_n_del_left;
        }
 
        if (MODE == DEBUG_MODE) write_log("trace_result_matching_fm(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
                                          + my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
    }
 
    void trace_result_matching_fi(int q, int v, int color_set_use, int n_del_left) {
        if (MODE == DEBUG_MODE) write_log("trace_result_matching_fi(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
                                          + my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
        if (MODE == DEBUG_MODE) write_log("with fi = " + my_double_to_string(fi[q][v][color_set_use][n_del_left]));
        inserted_nodes.push_back(v);
        int u = trace_fi_nxt_vertex[q][v][color_set_use][n_del_left];
        if (MODE == DEBUG_MODE) write_log("u = " + my_to_string(u) + "\n");
        if (u >= 0) {
            if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(u)
                                              + "=" + my_double_to_string(G.get_weight(v, u)));
            trace_result_matching_fm(q, u, color_set_use - (1 << color[v]), n_del_left);
        }
        else { //u < 0
            if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(-u-1)
                                              + "=" + my_double_to_string(G.get_weight(v, -u-1)));
            trace_result_matching_fi(q, -u - 1, color_set_use - (1 << color[v]), n_del_left);
        }
        if (MODE == DEBUG_MODE) write_log("trace_result_matching_fi(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
                                          + my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
    }
 
    void trace_result_matching_fd(int q, int v, int color_set_use, int n_del_left) {
        if (MODE == DEBUG_MODE) write_log("trace_result_matching_fd(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
                                          + my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
        if (MODE == DEBUG_MODE) write_log("with fd = " + my_double_to_string(fd[q][v][color_set_use][n_del_left]));
        int u = trace_fd_nxt_vertex[q][v][color_set_use][n_del_left];
        if (MODE == DEBUG_MODE) write_log("u = " + my_to_string(u) + "\n");
        int q_nxt = Q_tree.child[q][0];
        if (u == v) {
            trace_result_matching_fd(q_nxt, v, color_set_use, n_del_left - 1);
        }
        else if (u >= 0) {
            if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(u)
                                              + "=" + my_double_to_string(G.get_weight(v, u)));
            trace_result_matching_fm(q_nxt, u, color_set_use, n_del_left - 1);
        }
        else { // u < 0
            if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(-u-1)
                                              + "=" + my_double_to_string(G.get_weight(v, -u-1)));
            trace_result_matching_fi(q_nxt, -u - 1, color_set_use, n_del_left - 1);
        }
        if (MODE == DEBUG_MODE) write_log("trace_result_matching_fd(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
                                          + my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
    }
 
    void get_result() {
        if (MODE == DEBUG_MODE) write_log("get_result()...\n");
        double this_best_score = -INF;
        int root_map_to = -1, start_color_set = -1, start_n_del_left = -1;
        for(int v = 0; v < G.n; ++v)
            //map Q.root -> v
            for(int color_set_use = 0; color_set_use < (1 << n_colors); ++color_set_use)
                for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
                    if ((MODE == DEBUG_MODE) && (!equals(fm[Q_tree.root][v][color_set_use][n_del_left], -INF)))
                        write_log("fm(" + my_to_string(Q_tree.root) + "," + my_to_string(v) + "," + my_to_string(color_set_use) + "," +