[Python3] Break into cases and carefully count
Intuition\nFirst break into cases of the shape of the connected graph. Then break up pairs of houses into cases, e.g. pairs found inside of a loop, or pairs fou
# Intuition\nFirst break into cases of the shape of the connected graph. Then break up pairs of houses into cases, e.g. pairs found inside of a loop, or pairs found inside of a straight line.\n\n# Approach\nSee documentation in code.\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$ (Could be made $$O(1)$$ if not including output space by adding counts into output list directly).\n\n# Code\n```python\nclass Solution:\n    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:\n        answer = [0] * n\n        def add(array):\n            # Add the counts in prefix array `array` into `answer`.\n            for i, x in enumerate(array):\n                answer[i] += x\n        def add_line(length):\n            # Add the counts contributed to by pairs on a line.\n            add(range(2 * length, -1, -2))\n        def add_loop(loop):\n            # Add the counts contributed to by pairs in a loop.\n            if loop % 2 == 1:\n                add([2 * loop] * (loop // 2))\n            else:\n                add([2 * loop] * (loop // 2 - 1) + [loop])\n        def add_fork(prongs):\n            # Add the counts contributed to by pairs spanning across a fork.\n            # I.e. add pairs with one coming from line of length `prongs[0]`\n            #     and other coming from line of length `prongs[1]`, and\n            #     the prongs are connected by one house\n            # Looks like this: ---.-----\n            a = [0]\n            for i in range(2, sum(prongs) + 1):\n                a.append(2 * min(min(prongs), i - 1, sum(prongs) + 1 - i))\n            add(a)\n        def add_stemmed_fork(prongs):\n            # Add the counts contributed to by pairs spanning across a stemmed fork (stem size 1).\n            # I.e. add pairs with one coming from line of length `prongs[0]`\n            #     and other coming from line of length `prongs[1]`, and the prongs\n            #     are connected by a segment of length one.\n            # Looks like this: ---.-.-----\n            a = [0, 0]\n            for i in range(3, sum(prongs) + 2):\n                a.append(2 * min(min(prongs), i - 2, sum(prongs) + 2 - i))\n            add(a)\n            \n        x -= 1\n        y -= 1\n        x, y = min(x, y), max(x, y)\n        tails = sorted((x, n - 1 - y))\n        if x == y or x == y - 1:\n            # Just a line.\n            add_line(n - 1)\n        elif tails[1] == 0:\n            # A full loop.\n            #   __\n            #  /  \\\n            # |  n |\n            #  \\__/\n            # \n            add_loop(n)\n        elif tails[0] == 0:\n            # A one-tailed loop.\n            #   __\n            #  /  \\ ____tail\n            # |loop|\n            #  \\__/\n            tail = tails[1]\n            loop = n - tail\n            add_line(tail)\n            add_loop(loop)\n            add_fork((tail, (loop - 1) // 2))\n            add_fork((tail, loop // 2))\n        else:\n            # Two tails.\n            #   __\n            #  /  \\ ___tails[0]\n            # |loop|____tails[1]\n            #  \\__/\n            loop = n - sum(tails)\n            add_loop(loop)\n            add_line(tails[0])\n            add_line(tails[1])\n            add_stemmed_fork(tails)\n            add_fork((tails[0], (loop - 1) // 2))\n            add_fork((tails[0], loop // 2))\n            add_fork((tails[1], (loop - 1) // 2))\n            add_fork((tails[1], loop // 2))\n        return answer\n```
['Python3']