Luobuyu's Blog

0%

1617.统计子树中城市之间最大距离

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 2.5k 阅读时长 ≈ 2 分钟
二进制枚举子树，然后求树的直径，树的直径也有多种做法。

1617.统计子树中城市之间最大距离

题目描述：

给出n个城市，树状结构，给出edges表示双向边列表。一棵子树是城市的一个子集，且子集中任意城市之间可以通过子集中的其他城市和边到达。两个子树被认为不一样的条件是至少有一个城市在其中一棵子树中存在，但在另一棵子树中不存在。对于 d 从 1 到 n-1 ，请你找到城市间最大距离恰好为 d 的所有子树数目。

请你返回一个大小为 n-1 的数组，其中第 d 个元素（下标从 1 开始）是城市间最大距离恰好等于 d 的子树数目。

请注意，两个城市间距离定义为它们之间需要经过的边的数目。

数据范围：
$ 2\le n \le 15 $

题解：

由于数据范围比较小，可以直接用二进制状态枚举所有的子树，然后就是判断连通性（是不是子树），最后求出子树的直径。

枚举二进制： $ [1,(1<<n)-1] $ 。

判断连通性：从一个点 dfs 或 bfs ，如果能访问所有子树的点，则连通；否则不连通。有个更巧妙的做法，看做枚举边 $ [1, (1<<n)-1) $ ，直接判断点数是不是等于边数加一。（因为原结构已经是一个树了）。

求树的直径：先bfs或 dfs 找到最远的点，dfs的话代码量比较少（因为判断连通和求直径可以复用）。然后再从最远的点进行dfs 或bfs得到最大直径。也可以使用树形dp ，树形dp需要记录根节点子树的最大深度和次大深度，最后返回最大深度加次大深度。

树的直径

貌似点分治可以做数据范围更大的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
int t, n, m, k;
class Solution
{
public:
    const static int maxn = 1e1 + 10;
    const static int maxm = 1e5 + 10;
    vector<int> adj[maxn];
    int dfs(int u, int fa, int mask)
    {
        mask &= ~(1 << u);
        int dep = 0;
        for (int i = 0, v; i < adj[u].size(); ++i)
        {
            v = adj[u][i];
            if (v == fa)
                continue;
            if (mask & (1 << v))
            {
                dep = max(dep, dfs(v, u, mask) + 1);
            }
        }
        return dep;
    }
    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>> &edges)
    {
        vector<int> ans(n - 1);
        // 建图
        for (auto &edge : edges)
        {
            int u = edge[0] - 1;
            int v = edge[1] - 1;
            adj[u].emplace_back(v);
            adj[v].emplace_back(u);
        }
        // 直接枚举所有的子树，判断是否连通
        int all = (1 << n) - 1;
        for (int mask = 1; mask <= all; ++mask)
        {
            // i 是子树的二进制编码
            // bfs 该子树，判断是否连通
            int vis = mask;
            // 找到一个根
            int root;
            for (int i = 0; i < n; ++i)
            {
                if ((1 << i) & vis)
                {
                    root = i;
                    break;
                }
            }
            // root 是最大的顶点
            queue<int> q;
            q.push(root);
            vis &= ~(1 << root);
            int y;
            while (q.size())
            {
                y = q.front();
                q.pop();
                for (int i = 0, v; i < adj[y].size(); ++i)
                {
                    v = adj[y][i];
                    if (vis & (1 << v)) // 有边
                    {
                        vis &= ~(1 << v);
                        q.push(v);
                    }
                }
            }
            if (vis != 0) // 不是合法子树
                continue;
            int dep = dfs(y, -1, mask);
            if (dep == 0)
                continue;
            ans[dep - 1]++;
        }
        return ans;
    }
};

int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    Solution solution;
    read(n, m);
    vector<vector<int>> a;
    for (int i = 0, x, y; i < m; ++i)
    {
        vector<int> b;
        read(x, y);
        b.emplace_back(x);
        b.emplace_back(y);
        a.emplace_back(b);
    }
    for (auto &u : solution.countSubgraphsForEachDiameter(n, a))
    {
        cout << u << endl;
    }
    return 0;
}