二进制枚举 树形dp–树的直径
参考 树的最长路径
时间复杂度 $ O(n 2 ^ n) $
- 题目的数据很小,先枚举出来所有可能的子树(判断点是否联通)(又因为子树是生成树,通过枚举边,判断点的数量是否符合
nodenum = edgenum + 1
- 分类枚举,将枚举起点、终点 优化成
枚举顶点(中点)
- yxc的状态表示, 以u为顶点的所有路径 属性 :最大值
- 状态计算:d1 + d2为以该点(u)为顶点的最长路径 d1 为 最长子边,d2为次长子边,d为该结点(u)的最长边,
d = f(x) + 1
class Solution {
public:
int maxd;
vector<vector<int>> g;//邻接矩阵存储子树
int dfs(int u, int f) {//返回以u为顶点的最长边
int d1 = 0, d2 = 0;
for (auto v : g[u]) {
if (v == f) continue;
int d = dfs(v, u) + 1;//d为v为顶点最长边+v到u的距离
if (d >= d1) {
d2 = d1;
d1 = d;
}else if (d > d2) d2 = d;
}
maxd = max(maxd, d1 + d2);
return d1;
}
vector<int> countSubgraphsForEachDiameter(int& n, vector<vector<int>>& edges) {
vector<int> ans(n - 1, 0);
g.resize(n);
int st;//子树的一个随机根结点
for (int i = 1; i < 1 << n - 1; i ++) {
int edgen = 0, noden = 0;
for (int i = 0; i < n; i ++)
g[i].clear();//重新建子树
for (int j = 0; j < n - 1; j ++)
if (i & (1 << j)) {
int u = edges[j][0] - 1, v = edges[j][1] - 1;
edgen ++;
g[u].push_back(v);
g[v].push_back(u);
}
for (int j = 0; j < n; j ++)
if (g[j].size()) {
noden ++;
st = j;
}
if (edgen != noden - 1) continue;
maxd = 0;
dfs(st, -1);
ans[maxd - 1] ++;
}
return ans;
}
};