🎨 The ART of Dynamic Programming
\uD83C\uDFA8 The ART of Dynamic Programming: let cnt[i] be the count of nodes for each ith subtree, then we can use deductive reasoning to calculate the cardina
[\uD83C\uDFA8 The ART of Dynamic Programming:](https://leetcode.com/discuss/general-discussion/712010/The-ART-of-Dynamic-Programming-An-Intuitive-Approach%3A-from-Apprentice-to-Master) let `cnt[i]` be the count of nodes for each `i`<sup>th</sup> subtree, then we can use deductive reasoning to calculate the cardinality for the remaining connected components when each `i`<sup>th</sup> subtree root is removed, ie. the left/right subtree counts are trivial (the sum of `cnt[kids[i]]`), and we use inversion to the count of nodes "above" as the total node count minus the `i`<sup>th</sup> subtree count (`cnt[0] - cnt[i]`).  Note: `cnt[0]` == `N`.\n\n**\uD83D\uDED1Base case:** leaf nodes have no kids, so the count of each leaf node is `1`.\n\n**\uD83E\uDD14 Recurrence relation:** post-order traversal of the tree, and the `i`<sup>th</sup> subtree count is accumulated as the recursive stack unwinds, ie. `1` plus the count of all `j`<sup>th</sup> kids subtree counts.\n\n---\n\n*Kotlin*\n```\nclass Solution {\n    fun countHighestScoreNodes(P: IntArray): Int {\n        var N = P.size\n        var kid = Array(N){ mutableListOf<Int>() }\n        var cnt = LongArray(N){ 1 }\n        for (i in 1 until N)\n            kid[P[i]].add(i)\n        fun go(i: Int = 0): Long {\n            for (j in kid[i])\n                cnt[i] += go(j)\n            return cnt[i]\n        }\n        go()\n        var (best, hi) = Pair(mutableMapOf<Long, Int>(), 0L)\n        for (i in 0 until N) {\n            var t = Math.max(1L, N.toLong() - cnt[i])\n            for (j in kid[i])\n                t *= cnt[j]\n            best[t] = 1 + (best[t] ?: 0); hi = Math.max(hi, t)\n        }\n        return best[hi]!!\n    }\n}\n```\n\n*Javascript*\n```\nlet countHighestScoreNodes = (P, best = new Map(), hi = 0) => {\n    let N = P.length;\n    let kid = [...Array(N).keys()].map(i => []),\n        cnt = Array(N).fill(1);\n    for (let i = 1; i < N; ++i)\n        kid[P[i]].push(i);\n    let go = (i = 0) => {\n        for (let j of kid[i])\n            cnt[i] += go(j);\n        return cnt[i];\n    };\n    go();\n    for (let i = 0; i < N; ++i) {\n        let t = Math.max(1, N - cnt[i]);\n        for (let j of kid[i])\n            t *= cnt[j];\n        best.set(t, 1 + (best.get(t) || 0)), hi = Math.max(hi, t);\n    }\n    return best.get(hi);\n};\n```\n\n*Python3*\n```\nclass Solution:\n    def countHighestScoreNodes(self, P: List[int]) -> int:\n        N = len(P)\n        kids = defaultdict(set)\n        for i in range(1, N):\n            kids[P[i]].add(i)\n        cnt = [1] * N\n        def go(i = 0):\n            for j in kids[i]:\n                cnt[i] += go(j)\n            return cnt[i]\n        go()\n        best = Counter()\n        for i in range(N):\n            t = max(1, N - cnt[i])\n            for j in kids[i]:\n                t *= cnt[j]\n            best[t] += 1\n        return best[max(best.keys())]\n```\n\n*C++*\n```\nclass Solution {\npublic:\n    using LL = long long;\n    using VI = vector<int>;\n    using Map = unordered_map<int, int>;\n    using Adj = unordered_map<int, VI>;\n    using fun = function<int(int)>;\n    int countHighestScoreNodes(VI& P, Adj kids = {}, Map cnt = {}, Map best = {}, LL hi = 0) {\n        int N = P.size();\n        for (auto i{ 1 }; i < N; ++i)\n            kids[P[i]].push_back(i);\n        fun go = [&](auto i) {\n            for (auto j: kids[i])\n                cnt[i] += go(j);\n            return cnt[i] += 1;\n        };\n        go(0);\n        for (auto i{ 0 }; i < N; ++i) {\n            LL t = max(1, N - cnt[i]);\n            for (auto j: kids[i])\n                t *= cnt[j];\n            ++best[t], hi = max(hi, t);\n        }\n        return best[hi];\n    }\n};\n```
[]