HackerEarth Region Find problem solution

In this HackerEarth Region Find problem solution You are given a tree with N nodes and N-1 edges. We define a region as a set of nodes, such that if we remove all other nodes from the tree, these nodes still remain connected i.e. there exists a path between any two remaining nodes.

All the nodes have a weight associated to them. You are given Q queries. Each query has a number k. You have to find number of regions, such that the minimum weight among all the nodes of that region is exactly k. Output your answer modulo 109 + 7.

HackerEarth Region Find problem solution.

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define vi vector<int>
#define vs vector<string>
#define vpii vector<pii>
#define all(v) v.begin(), v.end()
#define gt greater<int>()
#define mod 1000000007
#define maxn 1555
 
ll dp[maxn][maxn];
int weight[maxn];
vi edges[maxn];
ll ans[maxn];
map<int,int> M;
 
void dfs(int u, int par){
  for(int i = 1; i <= weight[u]; i++){
    dp[u][i] = 1;
  }
  for(int i = 0, v; i < edges[u].size(); i++){
    v = edges[u][i];
    if(v != par){
      dfs(v,u);
      for(int k = 1; k <= weight[u]; k++){
        dp[u][k] = (dp[u][k] * (dp[v][k]+1)) % mod;
      }
    }
  }
}
 
int main(){
  int n,q,x,y;
  scanf("%d",&n);
  assert(n <= 1500);
  for(int i = 1; i <= n; i++){
    scanf("%d",&weight[i]);
    M[weight[i]];
  }
  int idx = 1;
  for(map<int,int>::iterator it = M.begin(); it != M.end(); it++){
    M[it->F] = idx;
    idx++;
  }
  for(int i = 1; i <= n; i++){
    weight[i] = M[weight[i]];
  }
  for(int i = 0; i < n-1; i++){
    scanf("%d %d",&x,&y);
    edges[x].pb(y);
    edges[y].pb(x);
  }
  dfs(1,0);
 
  for(int k = 1; k < maxn-1; k++){
    for(int i = 1; i <= n; i++){
      ans[k] = (ans[k]+dp[i][k]-dp[i][k+1]+mod) % mod;
    }
  }
 
  scanf("%d",&q);
  for(int i = 0; i < q; i++){
    scanf("%d",&x);
    if(M.count(x) == 0){
      cout << "0\n";
      continue;
    }
    x = M[x];
    cout << ans[x] << "\n";
  }
  return 0;
}