# HackerEarth Minimum Nodes problem solution

In this HackerEarth Minimum Nodes problem solution You are given a tree with N nodes and each node has some value assigned to it. Now you are given Q tasks of the form X K.
For each task, you have to find the path starting from X such that sum of nodes in the path is at least K and it contains minimum number of nodes. If such path exists, print the count of nodes in the path, else print -1.

## HackerEarth Minimum Nodes problem solution.

`#include<bits/stdc++.h>#define ll long long#define mp make_pair#define pb push_back#define si(x) scanf("%d",&x)#define pi(x) printf("%d\n",x)#define s(x) scanf("%lld",&x)#define p(x) printf("%lld\n",x)#define sc(x) scanf("%s",x)#define pc(x) printf("%s",x)#define pii pair<int,int>#define pll pair<ll,ll>#define F first#define S second#define inf 4e18#define prec(x) fixed<<setprecision(15)<<x#define all(x) x.begin(),x.end()#define rall(x) x.rbegin(),x.rend()#define mem(x,y) memset(x,y,sizeof(x))#define PQG priority_queue< int,std::vector<int>,std::greater<int> >#define PQL priority_queue< int,std::vector<int>,std::less<int> >#define PQPL priority_queue<pii ,vector< pii >, less< pii > >#define PQPG priority_queue<pii ,vector< pii >, greater< pii > >#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)using namespace std;const int N=1e5+7;vector<int>g[N];ll a[N],k;int ans,n,q;void dfs(int node,int par,ll sum,int cnt) {    sum+=a[node];    cnt++;    if(sum>=k) ans=min(ans,cnt);    for(int i=0;i<g[node].size();i++) {        int nxt=g[node][i];        if(nxt==par) continue;        dfs(nxt,node,sum,cnt);    }}int main() {    #ifndef ONLINE_JUDGE        freopen("in09.txt","r",stdin);        freopen("out09.txt","w",stdout);         #endif    cin>>n>>q;    assert(n>=1 && n<=100000);    assert(q>=1 && q<=10);    for(int i=1;i<=n;i++) {        cin>>a[i];        assert(a[i]>=1 && a[i]<=1000000000);    }    for(int i=1;i<n;i++) {        int u,v;        cin>>u>>v;        assert(u>=1 && u<=n);        assert(v>=1 && v<=n);        g[u].pb(v);        g[v].pb(u);    }    while(q--) {        int src;         cin>>src>>k;        ans=INT_MAX;        dfs(src,0,0,0);        if(ans==INT_MAX) ans=-1;        cout<<ans<<endl;    }        return 0;}`

### Second solution

`#include<bits/stdc++.h>#define ll long longusing namespace std;int val[100005],n,q,r,k;vector<int>v[100005];bool vis[100005];int fin=100005;void init(){    fin=100005;    for(int i=1;i<=100000;i++)vis[i]=0;}void dfs(int r,int value,int cnt){    if(value-val[r]<=0){fin=min(fin,cnt+1);return;}    vis[r]=1;cnt++;bool f=0;    for(auto i:v[r])    {        if(vis[i])continue;        dfs(i,value-val[r],cnt);    }}int main(){       cin>>n>>q;    for(int i=1;i<=n;i++)cin>>val[i];    for(int i=1;i<n;i++)    {        int x,y;        cin>>x>>y;        v[y].push_back(x);        v[x].push_back(y);      }    while(q--)    {        init();        cin>>r>>k;        dfs(r,k,0);        cout<<fin<<"\n";    }    return 0;}`