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;}`