跳转至

小美的区域会议#
发布于2021-04-16
上次编辑2021-04-16

问题描述#

小美是美团总部的高管，她想要召集一些美团的区域负责人来开会，已知美团的业务区域划分可以用一棵树来表示，树上有 n 个节点，每个节点分别代表美团的一个业务区域，每一个区域有一个负责人，这个负责人的级别为 A[i]
已知小美召集人员开会必须满足以下几个条件：
1.小美召集的负责人所在的区域必须构成一个非空的连通的图，即选取树上的一个连通子图。
2.这些负责人中，级别最高的和级别最低的相差不超过 k 。
请问小美有多少种召集负责人的方式，当且仅当选取的集合不同时我们就认为两种方式不同。由于方案数可能非常大，所以请对 10^9+7 取模。

格式：

输入：
- 输入第一行包含两个整数 n 和 k ，表示区域的数量，和不能超过的级别。
- 接下来有 n-1 行，每行有两个正整数 a 和 b ，表示 a 号区域和 b 号区域有一条边。
- 最后一行有 n 个整数，第 i 个整数表示 i 号区域负责人的级别。
输出：
- 输出仅包含一个整数，表示可以选择的方案数对 10^9+7 取模之后的结果。

示例：

输入：
     5 1
     1 2
     2 3
     3 4
     4 5
     2 2 2 2 2
输出：15
解释：显然一个区域的方案有 {1}，{2}，{3}，{4}，{5}，两个区域的方案有 4 个，三个区域的方案有 3 个，四个区域的方案有 2 个，五个区域的方案有 1 个，共 15 个。

提示：

  • 1 <= n, k <= 2000
  • 1 <= a, b <= n

解题思路#

方法一：DFS#

关键在于确保搜索到所有解，不要重复也不要漏解。

 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
import sys
from typing import List

readline = sys.stdin.readline


def readint() -> int:
    return int(readline().strip())


def readstr() -> str:
    return readline().strip()


def readints() -> List[int]:
    return list(map(int, readline().strip().split()))


n, k = readints()
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = readints()
    adj[u].append(v)
    adj[v].append(u)
o = [0] + readints()
MOD = 10 ** 9 + 7


def dfs(s: int, u: int) -> int:
    vis[u] = True
    ans = 1
    for v in adj[u]:
        if not vis[v] and (
            (o[v] > o[s] and o[v] - o[s] <= k) or (o[v] == o[s] and v < s)
        ):
            ans = (ans * (1 + dfs(s, v))) % MOD
    return ans


ans = 0
for i in range(1, n + 1):
    vis = [False] * (n + 1)
    ans = (ans + dfs(i, i)) % MOD
print(ans)

 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
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<vector<int>> adj(n + 1);
    vector<int> o(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    for (int i = 1; i <= n; ++i) {
        cin >> o[i];
    }
    int MOD = 1e9 + 7;
    vector<int> vis(n + 1);
    function<long long(int, int)> dfs = [&](int s, int u) {
        vis[u] = 1;
        long long ans = 1;
        for (int v : adj[u]) {
            if (!vis[v] && ((o[v] > o[s] && o[v] - o[s] <= k) ||
                            (o[v] == o[s] && v < s))) {
                ans = (ans * (1 + dfs(s, v))) % MOD;
            }
        }
        return ans;
    };
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        vis.assign(n + 1, 0);
        ans = (ans + dfs(i, i)) % MOD;
    }
    cout << ans << '\n';
    return 0;
}
返回顶部

在手机上阅读