public class Main {

    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    /*
     * normal:
     * Bina zero operation ke current node se neeche
     * jaane wale maximum path ka sum.
     *
     * modified:
     * At most ek node ko 0 karke current node se neeche
     * jaane wale maximum path ka sum.
     */
    static class State {
        long normal;
        long modified;

        State(long normal, long modified) {
            this.normal = normal;
            this.modified = modified;
        }
    }

    static long ans;

    public static long maxPathSum(TreeNode root) {

        ans = Long.MIN_VALUE;

        dfs(root);

        return ans;
    }

    private static State dfs(TreeNode root) {

        if (root == null) {
            return new State(
                Long.MIN_VALUE / 4,
                Long.MIN_VALUE / 4
            );
        }

        State left = dfs(root.left);
        State right = dfs(root.right);

        /*
         * Negative child ko path mein lena compulsory nahi hai.
         *
         * Isliye negative contribution ko 0 kar dete hain.
         */
        long leftNormal = Math.max(0L, left.normal);
        long rightNormal = Math.max(0L, right.normal);


        // =====================================================
        // STATE 1: Bina zero operation ke downward path
        // =====================================================

        /*
         * Current node se parent ki taraf return karte waqt
         * sirf ONE child choose kar sakte hain.
         *
         * root
         *  / \
         * L   R
         *
         * Path:
         * root -> L
         * OR
         * root -> R
         */
        long normal =
                root.val + Math.max(leftNormal, rightNormal);


        // =====================================================
        // STATE 2: At most one node ko zero karne ke baad
        // downward path
        // =====================================================

        /*
         * CASE 1:
         * Current node ko 0 kar diya.
         *
         * IMPORTANT:
         * Yahan bhi sirf ONE child le sakte hain,
         * because ye value parent ko return hogi.
         *
         *  L
         *  |
         *  0
         *
         * OR
         *
         *  0
         *   |
         *   R
         */
        long modifyCurrent =
                Math.max(leftNormal, rightNormal);


        /*
         * CASE 2:
         * Zero operation left subtree mein use hua.
         *
         * Current node normal rahega.
         */
        long modifyLeft =
                root.val + left.modified;


        /*
         * CASE 3:
         * Zero operation right subtree mein use hua.
         */
        long modifyRight =
                root.val + right.modified;


        /*
         * "At most one" ka matlab:
         * zero operation use na karna bhi allowed hai.
         */
        long modified =
                Math.max(
                    normal,
                    Math.max(
                        modifyCurrent,
                        Math.max(modifyLeft, modifyRight)
                    )
                );


        // =====================================================
        // COMPLETE PATH CASES
        // =====================================================

        /*
         * Ab hum parent ko value return nahi kar rahe.
         *
         * Yahan complete path ban sakta hai:
         *
         *       L
         *        \
         *         root
         *        /
         *       R
         *
         * Isliye LEFT + ROOT + RIGHT allowed hai.
         */

        // CASE 1: Normal complete path
        long normalThrough =
                leftNormal +
                root.val +
                rightNormal;


        // CASE 2: Current node ko zero kar diya
        long specialAtCurrent =
                leftNormal +
                rightNormal;


        // CASE 3: Zero left subtree mein hai
        long specialInLeft =
                left.modified +
                root.val +
                rightNormal;


        // CASE 4: Zero right subtree mein hai
        long specialInRight =
                leftNormal +
                root.val +
                right.modified;


        // Global answer update
        ans = Math.max(ans, normalThrough);
        ans = Math.max(ans, specialAtCurrent);
        ans = Math.max(ans, specialInLeft);
        ans = Math.max(ans, specialInRight);


        /*
         * Parent ko sirf downward path return karna hai.
         *
         * Complete path return nahi kar sakte,
         * because parent usko further extend nahi kar sakta.
         */
        return new State(normal, modified);
    }


    public static void main(String[] args) {

        /*
                 5
               /   \
            -50     5
            /  \
           5    5

        Zero operation:
        -50 -> 0

        Best path:

        5 -> 0 -> 5 -> 5

        Sum = 5 + 0 + 5 + 5
            = 15
        */

        TreeNode root = new TreeNode(5);

        root.left = new TreeNode(-50);
        root.right = new TreeNode(5);

        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(5);

        System.out.println(maxPathSum(root));
    }
}