just found this question can use dp and O(n^5)?
following code is from other guys, it passed using just 16ms\nand I think dp[x][k][y] is degree from x to y as k is intermediary node. I guess\nO(n^5) is just m
following code is from other guys, it passed using just 16ms\nand I think dp[x][k][y] is degree from x to y as k is intermediary node. I guess\nO(n^5) is just my guess, still digesting the code\nBTW my code takes about 520ms and I know why I cannot get Google offer, LOL.\n\n```\n#define  _CRT_SECURE_NO_WARNINGS\n#define _USE_MATH_DEFINES\n#define _SILENCE_ALL_CXX17_DEPRECATION_WARNINGS\n#pragma GCC target("avx2")\n#pragma GCC optimize("O3")\n#pragma GCC optimize("unroll-loops")\n#pragma comment (linker, "/STACK:526000000")\n#include "bits/stdc++.h"\nusing namespace std;\ntypedef string::const_iterator State;\n#define eps 1e-8L\n#define MAX_MOD 1000000007LL\n#define GYAKU 500000004LL\n#define MOD 998244353LL\n#define pb push_back\n#define mp make_pair\ntypedef long long ll;\ntypedef long double ld;\n#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))\n#define ALL(x) (x).begin(),(x).end()\nunsigned long xor128() {\n\tstatic unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;\n\tunsigned long t = (x ^ (x << 11));\n\tx = y; y = z; z = w;\n\treturn (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));\n};\n\nclass Solution {\npublic:\n\tvector<int> vertexs[30];\n\tint used[30] = {};\n\tint sizing[30] = {};\n\tint dp[30][30][30];\n\tvoid dfs(int now, int back) {\n\t\tvector<int> can_go;\n\t\tsizing[now] = 1;\n\t\tfor (auto& x : vertexs[now]) {\n\t\t\tif (x == back or used[x]) continue;\n\t\t\tdfs(x, now);\n\t\t\tcan_go.push_back(x);\n\t\t}\n\t\tREP(i, 30) {\n\t\t\tREP(q, 30) {\n\t\t\t\tdp[now][i][q] = 0;\n\t\t\t}\n\t\t}\n\t\tfor (auto& x : can_go) {\n\t\t\tint cnts[30][30] = {};\n\t\t\tREP(j, sizing[x] + 1) {\n\t\t\t\tREP(t, sizing[x] + 1) {\n\t\t\t\t\tcnts[j + 1][max(t, j + 1LL)] += dp[x][j][t];\n\t\t\t\t}\n\t\t\t}\n\t\t\tREP(i, sizing[now]) {\n\t\t\t\tREP(q, sizing[now]) {\n\t\t\t\t\tcnts[i][q] += dp[now][i][q];\n\t\t\t\t}\n\t\t\t}\n\t\t\tREP(i, sizing[now]) {\n\t\t\t\tREP(q, sizing[now]) {\n\t\t\t\t\tif (dp[now][i][q] == 0) continue;\n\t\t\t\t\tREP(j, sizing[x]) {\n\t\t\t\t\t\tREP(t, sizing[x]) {\n\t\t\t\t\t\t\tint rights = max({ q,t,i + j + 1 });\n\t\t\t\t\t\t\tif (rights < 30)\n\t\t\t\t\t\t\t\tcnts[max(i, j + 1)][rights] += dp[now][i][q] * dp[x][j][t];\n\t\t\t\t\t\t}\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t\tswap(cnts, dp[now]);\n\t\t\tsizing[now] += sizing[x];\n\t\t}\n\t\tdp[now][0][0] = 1;\n\t\treturn;\n\t}\n\tvector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {\n\t\tREP(i, n) {\n\t\t\tvertexs[i].clear();\n\t\t\tused[i] = 0;\n\t\t}\n\t\tREP(i, edges.size()) {\n\t\t\tedges[i][0]--;\n\t\t\tedges[i][1]--;\n\t\t\tvertexs[edges[i][0]].push_back(edges[i][1]);\n\t\t\tvertexs[edges[i][1]].push_back(edges[i][0]);\n\t\t}\n\t\tvector<int> ans(n - 1, 0);\n\t\tREP(i, n) {\n\t\t\tdfs(i, -1);\n\t\t\tused[i] = 1;\n\t\t\tREP(q, 30) {\n\t\t\t\tREP(j, n - 1) {\n\t\t\t\t\tans[j] += dp[i][q][j + 1];\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\treturn ans;\n\t}\n};\n```\n\n
[]