小美的区域会议

[编程题]小美的区域会议

热度指数：772 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美是美团总部的高管，她想要召集一些美团的区域负责人来开会，已知美团的业务区域划分可以用一棵树来表示，树上有n个节点，每个节点分别代表美团的一个业务区域，每一个区域有一个负责人，这个负责人的级别为A_i

已知小美召集人员开会必须满足以下几个条件：

1. 小美召集的负责人所在的区域必须构成一个非空的连通的图，即选取树上的一个连通子图。

2. 这些负责人中，级别最高的和级别最低的相差不超过k。

请问小美有多少种召集负责人的方式，当且仅当选取的集合不同时我们就认为两种方式不同。由于方案数可能非常大，所以请对10^9+7取模。

输入描述:

输入第一行包含两个整数n和k，表示区域的数量，和不能超过的级别。(1<=n,k<=2000)
接下来有n-1行，每行有两个正整数a和b，表示a号区域和b号区域有一条边。(1<=a,b<=n)
最后一行有n个整数，第i个整数表示i号区域负责人的级别。

输出描述:

输出仅包含一个整数，表示可以选择的方案数对10^9+7取模之后的结果。

示例1

输入

输出

说明

显然一个区域的方案有{1}，{2}，{3}，{4}，{5},两个区域的方案有4个，三个区域的方案有3个，四个区域的方案有2个，五个区域的方案有1个，共15个。

算法知识视频讲解

Java

牛客340512146号

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        Set<Integer>[]tree = new HashSet[n];
        for(int i=0;i<n;i++){
            tree[i] = new HashSet<>();
        }
        for(int i=0;i<n-1;i++){
            int a = sc.nextInt()-1;
            int b = sc.nextInt()-1;
            tree[a].add(b);
            tree[b].add(a);
        }
        int[]r = new int[n];
        for(int i=0;i<n;i++){
            r[i] = sc.nextInt();
        }
        long ans = 0;
        for(int i=0;i<n;i++){
            boolean[]visited = new boolean[n];
            long a = dfs(tree,visited,i,r,k,r[i],i);
            ans  = (ans+a)%1000000007;
        }
        System.out.println(ans);
    }
    public static long dfs(Set<Integer>[]tree,boolean[]visited,int i,int[]r,int k,int k0,int i0){
        visited[i] = true;
        long a = 1;
        for(int j:tree[i]){
            if(!visited[j]&&r[j]>=k0&&r[j]-k0<=k&&(r[j]>k0||j<i0))
                a = (a*(1+dfs(tree,visited,j,r,k,k0,i0)))%1000000007;
        }
        return a;
    }
}

发表于 2021-03-22 09:18:23 回复(2)