using System;

public class Program

{

    public class TreeNode 

    {

        public int val;

        public TreeNode left;

        public TreeNode right;

        public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {

            this.val = val;

            this.left = left;

            this.right = right;

        }

    }

    private static long max = 0;

    private static long FindTotal(TreeNode root)

    {

        if(root == null) 

            return 0;

        return FindTotal(root.left) + FindTotal(root.right) + root.val;

    }

​

    private static long FindMax(TreeNode root, long sum)

    {

        if(root == null) 

            return 0;

        long localSum = FindMax(root.left, sum) + FindMax(root.right, sum) + root.val;

        max = Math.Max(max, localSum * (sum - localSum));

        return localSum;

    }

​

    public static int FindMaxProduct(TreeNode root) 

    {

        long totalSum = FindTotal(root);

        FindMax(root, totalSum);

        return (int)(max);

    }

    public static void Main()

    {

        Console.WriteLine("UniLecs");

        // tests

        var root = new TreeNode(1);

        root.left = new TreeNode(2);

        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);

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

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

        Console.WriteLine(FindMaxProduct(root)); // 110

    }

}