HackerEarth Isomorphic Trees problem solution

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Stream;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        IsomorphicTrees solver = new IsomorphicTrees();
        solver.solve(1, in, out);
        out.close();
    }

    static class IsomorphicTrees {
        int[] n;
        List<Integer>[][] g;
        public int[][][][] dp;
        public int[][][] sz;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            n = new int[2];
            n[0] = in.nextInt();
            n[1] = in.nextInt();
            g = new List[2][];
            g[0] = LUtils.genArrayList(n[0] + 1);
            g[1] = LUtils.genArrayList(n[1] + 1);
            for (int k = 0; k < 2; k++) {
                for (int i = 0; i < n[k] - 1; i++) {
                    int a = in.nextInt(), b = in.nextInt();
                    g[k][a].add(b);
                    g[k][b].add(a);
                }
            }
            dp = new int[n[0] + 1][n[0] + 1][n[1] + 1][n[1] + 1];
            sz = new int[2][][];
            sz[0] = new int[n[0] + 1][n[0] + 1];
            sz[1] = new int[n[1] + 1][n[1] + 1];
            AUtils.deepFill(dp, -1);
            AUtils.deepFill(sz, -1);
            for (int i = 1; i <= n[0]; i++) {
                for (int j = 1; j <= n[1]; j++) {
                    if (j != 1) out.print(" ");
                    out.print(solve(0, i, 0, j));
                }
                out.println();
            }
        }

        public int getSize(int k, int p, int c) {
            if (sz[k][p][c] != -1) return sz[k][p][c];
            int r = 1;
            for (int n : g[k][c]) {
                if (p == n) continue;
                r += getSize(k, c, n);
            }
            return sz[k][p][c] = r;
        }

        public int solve(int p1, int c1, int p2, int c2) {
            if (dp[p1][c1][p2][c2] != -1) return dp[p1][c1][p2][c2];
            int s1 = g[0][c1].size() - (p1 == 0 ? 0 : 1);
            int s2 = g[1][c2].size() - (p2 == 0 ? 0 : 1);

            int n = Math.max(s1, s2);

            int[][] mat = new int[n + 1][n + 1];
            int id1 = 1;
            for (int n1 : g[0][c1]) {
                if (n1 == p1) continue;
                int id2 = 1;
                for (int n2 : g[1][c2]) {
                    if (n2 == p2) continue;
                    mat[id1][id2] = solve(c1, n1, c2, n2);
                    id2++;
                }
                id1++;
            }
            id1 = 1;
            for (int n1 : g[0][c1]) {
                if (n1 == p1) continue;
                int t = getSize(0, c1, n1);
                for (int j = s2 + 1; j <= s1; j++) mat[id1][j] = t;
                id1++;
            }
            int id2 = 1;
            for (int n2 : g[1][c2]) {
                if (n2 == p2) continue;
                int t = getSize(1, c2, n2);
                for (int j = s1 + 1; j <= s2; j++) mat[j][id2] = t;
                id2++;
            }
            return dp[p1][c1][p2][c2] = Hungarian.minWeightPerfectMatching(mat);
        }

    }

    static class AUtils {
        public static void deepFill(int[][][][] x, int val) {
            for (int[][][] y : x) deepFill(y, val);
        }

        public static void deepFill(int[][][] x, int val) {
            for (int[][] y : x) deepFill(y, val);
        }

        public static void deepFill(int[][] x, int val) {
            for (int[] y : x) deepFill(y, val);
        }

        public static void deepFill(int[] x, int val) {
            Arrays.fill(x, val);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1 << 16];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void println() {
            writer.println();
        }

        public void close() {
            writer.close();
        }

        public void print(int i) {
            writer.print(i);
        }

    }

    static class LUtils {
        public static <E> List<E>[] genArrayList(int size) {
            return Stream.generate(ArrayList::new).limit(size).toArray(List[]::new);
        }

    }

    static class Hungarian {
        public static int minWeightPerfectMatching(int[][] a) {
            int n = a.length - 1;
            int m = a[0].length - 1;
            int[] u = new int[n + 1];
            int[] v = new int[m + 1];
            int[] p = new int[m + 1];
            int[] way = new int[m + 1];
            for (int i = 1; i <= n; ++i) {
                int[] minv = new int[m + 1];
                Arrays.fill(minv, Integer.MAX_VALUE);
                boolean[] used = new boolean[m + 1];
                p[0] = i;
                int j0 = 0;
                while (p[j0] != 0) {
                    used[j0] = true;
                    int i0 = p[j0];
                    int delta = Integer.MAX_VALUE;
                    int j1 = 0;
                    for (int j = 1; j <= m; ++j)
                        if (!used[j]) {
                            int d = a[i0][j] - u[i0] - v[j];
                            if (minv[j] > d) {
                                minv[j] = d;
                                way[j] = j0;
                            }
                            if (delta > minv[j]) {
                                delta = minv[j];
                                j1 = j;
                            }
                        }
                    for (int j = 0; j <= m; ++j)
                        if (used[j]) {
                            u[p[j]] += delta;
                            v[j] -= delta;
                        } else
                            minv[j] -= delta;
                    j0 = j1;
                }
                while (j0 != 0) {
                    int j1 = way[j0];
                    p[j0] = p[j1];
                    j0 = j1;
                }
            }
            int[] matching = new int[n + 1];
            for (int i = 1; i <= m; ++i)
                matching[p[i]] = i;
            return -v[0];
        }

    }
}