TCO 2015 2B MinimumCuts

public class MinimumCuts
{
    int N;
    Node[] nodes;
    static final int MXVAL = 10000;
    static final int[][] orders = {
        {0, 1, 2},
        {0, 2, 1},
        {1, 0, 2},
        {1, 2, 0},
        {2, 0, 1},
        {2, 1, 0}
    };

    private class Node
    {
        Node left, right;
        int removeCost;
        int[] dp;

        void give(Node n)
        {
            if (left == null)
                left = n;
            else if (right == null)
                right = n;
            else
                throw new RuntimeException();
        }

        int f(int x)
        {
            return Math.min(dp[x], removeCost + x);
        }

        void solve()
        {
            if  (left != null)  left.solve();
            if (right != null) right.solve();
            dp = new int[MXVAL * 2 + 1];
            for (int x = 0; x < dp.length; x++)
            {
                if (left == null)
                    dp[x] = (int) 1e8;
                else if (right == null)
                {
                    int x1 = left.f(Math.min(removeCost, x));
                    int x2 = Math.min(x, removeCost + left.f(0));
                    dp[x] = Math.max(dp[x], x1);
                    dp[x] = Math.max(dp[x], x2);
                }
                else
                {
                    for (int[] or : orders)
                    {
                        int v = 0;
                        for (int n : or)
                        {
                            if (n == 0)
                                v = left.f(v);
                            else if (n == 1)
                                v = right.f(v);
                            else
                                v = Math.min(x, removeCost + v);
                        }
                        dp[x] = Math.max(dp[x], v);
                    }
                }
            }
        }
    }

    public int costPaid(int[] parent, int[] cost)
    {
        this.N = cost.length + 1;
        nodes = new Node[N];
        for (int i = 0; i < N; i++)
            nodes[i] = new Node();
        for (int i = 0; i < N-1; i++)
        {
            nodes[i+1].removeCost = cost[i];
            nodes[parent[i]].give(nodes[i+1]);
        }
        nodes[0].solve();
        return nodes[0].dp[0];
    }
}