leetcode 困难题 1617. 统计子树中城市之间最大距离

Problem: 1617. 统计子树中城市之间最大距离n比较小可以找出边数组edges的所有排列组合使用回溯dfs函数排列组合放在数组tr中然后对任何一种组合求出邻接表任意从一个顶点开始访问统计访问的顶点数量cnt用bit表示用到的所有顶点mask最后若cnt nbit.count()也就是不存在多棵树只有一棵树将统计结果累加mxxx就是树中路径的最大的长度Codeclass Solution { public: vectorvectorint tr; vectorint tmp, ret; void dfs(int n) { if(n-1) { if(tmp.size() 1) tr.push_back(tmp); return; } tmp.push_back(n); dfs(n-1); tmp.pop_back(); dfs(n-1); } int mxxx, cnt; int recursion(vectorvectorint arr, int pre, int start, int h) { int r, mx INT_MIN; priority_queueint, vectorint, decltype(greaterint()) pq; cnt; for(int next : arr[start]) { if(next ! pre) { r recursion(arr, start, next, h 1) 1; pq.push(r); if(pq.size() 2) pq.pop(); } } if(pq.size()0) return 0; int a 0, c 0; a pq.top(); pq.pop(); if(!pq.empty()) c pq.top(); mxxx max(mxxx, a c); return max(a, c); } vectorint countSubgraphsForEachDiameter(int n, vectorvectorint edges) { dfs(n-2); ret.assign(n-1, 0); ret[0] n-1; int a, c, ind, len; for(vectorint t : edges) { t[0]--; t[1]--; } for(int i 0; i tr.size(); i) { vectorvectorint arr(n); mxxx INT_MIN; len tr[i].size(); cnt 0; int mask 0; for(int j 0; j len; j) { ind tr[i][j]; a edges[ind][0]; c edges[ind][1]; arr[a].push_back(c); arr[c].push_back(a); mask | (1a); mask | (1c); } bitset32 nbit(mask); recursion(arr, -1, a, 0); if(mxxx 1 cnt nbit.count()) ret[mxxx - 1]; } return ret; } };