Beat 100% | O(n^3) | DP | BFS + DFS | Iterate diameters | Explained
Intuition\n Describe your first thoughts on how to solve this problem. \nVery hard. My respect for those who come up with this approach.\n  \n# Approach\n Descr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nVery hard. My respect for those who come up with this approach.\n  \n# Approach\n<!-- Describe your approach to solving the problem. -->\nFirst we need to know neighbors for each city, so create an adjacency list.\nNext we need to know distance between any two cities. Create 2d array distances using BFS.\n\n**Main idea:**\nFor every pair of cites calculate number subtrees between, such that maximum distance in subtree less or equal diameter.\n![example](https://assets.leetcode.com/uploads/2020/09/21/p1.png)\nTake **1 and 2 as diameter**. There is only one subtree because distance from 3 or 4 to 1 is more than the diameter.\nLet\'s take **1 and 3 as diameter**. How many  subtrees between 1 and 3? There are two subtrees (we have to choose 2, but 4 is optional).\nWe can use DFS to calculate number of subtrees. \nStart from 1 look for adjacent.\nDistance from 2 to 1 plus distance from 2 to 3 equals the diameter, so we have to choose 2.\nDistance from 4 to 1 plus distance from 4 to 3 more than the diameter, so 4 is optional. Multiply number subtrees by 2.\nHowever, if we take **1 and 4 as diameter** we count full tree twice. How to avoid such situation? We can iterate cities in increasing order and when distance to any diameter edge equals the diameter choose city only if it is greater than other edge.\nDistance from 1 to 3 is equal the diameter, but 3 less than 4 so we cannot choose 3.\n\n**More complex example:**\n![example](https://raw.githubusercontent.com/narfuls/leet-image/main/Diameter.PNG)\n3 and 8 edges of diameter (d=4)\n```\ndist[5][3] + dist[5][8] == d\ndist[1][3] + dist[1][8] == d \ndist[10][3] + dist[10][8] == d\n```\nWe have to choose cities 5, 1 and 10. \n```\ndist[13][3] > d\ndist[14][8] > d\n```\nWe cannot choose cities 13 and 14. \n```\ndist[4][3] == d but 4 < 8\ndist[6][3] == d but 6 < 8\n```\nWe cannot choose cities 4 and 6. \n```\ndist[7][8] == d and 7 > 3\ndist[9][3] == d and 9 > 8\ndist[12][3] == d and 12 > 8\n```\nWe may choose or not to choose cities 7,9 and 12. \n```\ndist[2][3] < d and dist[2][8] < d\ndist[11][3] < d and dist[11][8] < d\n```\nWe may choose or not to choose cities 2 and 11. \n\n**DFS addition value is 0** for required(1, 5 and 10).\n**DFS addition value is 1** for optional(2, 7, 9, 11 and 12)\nForbidden(4, 6,13 and 14) shold be excluded from DFS.\n\n**Number of subtrees between 3 and 8 is DFS(3)**\n```\nDFS(3) == 0 + DFS(5)\nDFS(5) == 0 + DFS(7) * DFS(1)\nDFS(7) == 1 + 1\nDFS(1) == 0 + DFS(2) * DFS(10) * DFS(11)\nDFS(2) == 1 + DFS(9)\nDFS(9) == 1 + 1\nDFS(10) == 0 + 1 // 6 and 8 is forbidden\nDFS(11) == 1 + DFS(12)\nDFS(12) == 1 + 1\n```\n# Complexity\n- Time complexity: O(n^3)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n^2)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\npublic class Solution {\n    private byte[][] dist;\n    private List<byte>[] adj;\n    private void InitAdjecency(int n, int[][] edges)\n    {\n        adj = Enumerable.Repeat(0, n).Select(_ => new List<byte>()).ToArray();\n        foreach (var edge in edges)\n        {\n            adj[edge[0] - 1].Add((byte)(edge[1] - 1));\n            adj[edge[1] - 1].Add((byte)(edge[0] - 1));\n        }\n\n    }\n    private void DistanceBFS(byte[] disI, byte cur, byte prev)\n    {\n        foreach (byte next in adj[cur])\n        {\n            if (next != prev)\n            {\n                disI[next] = disI[cur]; \n                disI[next]++;\n                DistanceBFS(disI, next, cur);\n            }\n        }\n    }\n    private void InitDistance(int n)\n    {\n        dist = new byte[n][];\n        for (byte i = 0; i < n; i++)\n        {\n            dist[i] = new byte[n];\n            DistanceBFS(dist[i], i, i);\n        }\n    }\n    private int DFS(byte i, byte j, byte cur, byte prev)\n    {\n        int optionalValue = dist[i][cur] + dist[j][cur] > dist[i][j] ? 1 : 0;\n        int res = 1;\n        foreach (byte next in adj[cur])\n        {\n            if (next != prev &&\n               (dist[i][next] < dist[i][j] || dist[i][next] == dist[i][j] && next > j) &&\n               (dist[j][next] < dist[i][j] || dist[j][next] == dist[i][j] && next > i)) \n                res *= DFS(i, j, next, cur);\n        }\n        return res + optionalValue;\n    }\n    public int[] CountSubgraphsForEachDiameter(int n, int[][] edges)\n    {\n        InitAdjecency(n, edges);\n        InitDistance(n);\n        var res = new int[n-1];\n        res[0] = n - 1;\n        for (byte i = 0; i < n; i++)\n        {\n            for (byte j = (byte)(i + 1); j < n; j++)\n            {\n                if(dist[i][j] > 1)\n                    res[dist[i][j] - 1] += DFS(i, j, i, 255);\n            }\n        }\n        return res;\n    }\n}\n```
['Dynamic Programming', 'C#']