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


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