# HackerEarth King Arthur’s Kingdom problem solution

In this HackerEarth King Arthur’s Kingdom problem solution You are given a tree consisting of N nodes and another integer K, where the ith node has value equal to v[i].

Now, we call the value of a sub-tree the number of distinct v[i] among all nodes it contains. You need to find the number of sub-trees of this tree having value <= K.

A sub-tree of a tree is a subset of nodes and edges of the tree that form a single connected component.

## HackerEarth King Arthur’s Kingdom problem solution.

`#include <bits/stdc++.h>#define FOR(i, s, e) for(int i=s; i<e; i++)#define loop(i, n) for(int i=0; i<n; i++)#define CIN   ios_base::sync_with_stdio(0); cin.tie(0)#define getint(n) scanf("%d", &n)#define pb(a) push_back(a)#define ll long long int#define ull unsigned long long int#define dd double#define SZ(a) int(a.size())#define read() freopen("input.txt", "r", stdin)#define write() freopen("output.txt", "w", stdout)#define mem(a, v) memset(a, v, sizeof(a))#define all(v) v.begin(), v.end()#define Unique(x)  x.erase(unique(all(x)), x.end())#define pi acos(-1.0)#define pf printf#define sf scanf#define mp make_pair#define paii pair<int, int>#define padd pair<dd, dd>#define pall pair<ll, ll>#define fr first#define sc second#define CASE(n) printf("Case %d: ",++n)#define CASE_COUT cout<<"Case "<<++cas<<": "#define inf 1000000000#define EPS 1e-9#define Harmonic(n) (0.577215664901532+log(n)+(1/(2*n)))     ///Use Only for large n#define mx 100005using namespace std;//8 way moves//int fx[]={0,0,1,-1,1,1,-1,-1};//int fy[]={1,-1,0,0,1,-1,1,-1};//knight moves//int fx[]={-2,-2,-1,-1,1,1,2,2};//int fy[]={-1,1,-2,2,-2,2,-1,1};//Bit operationint SET(int n,int pos){ return n=n | (1<<pos);}int RESET(int n,int pos){ return n=n & ~(1<<pos);}int CHECK(int n,int pos){ return (bool) (n & (1<<pos));}int str2int(string s) {    stringstream ss(s);    int x;    ss >> x;    return x;}string int2str(int a) {    stringstream ss;    ss << a;    string str = ss.str();    return str;}string char2str(char a) {    stringstream ss;    ss << a;    string str = ss.str();    return str;}ll bigMod(ll n,ll power,ll MOD){    if(power==0)        return 1;    if(power%2==0)    {        ll ret=bigMod(n,power/2,MOD);        return ((ret%MOD)*(ret%MOD))%MOD;    }    else return ((n%MOD)*(bigMod(n,power-1,MOD)%MOD))%MOD;}// ll modInverse(ll n,ll MOD)// {//     return bigMod(n,MOD-2,MOD);// }ll modInverse(ll a, ll m){    ll m0 = m, t, q;    ll x0 = 0, x1 = 1;    if (m == 1)      return 0;    while (a > 1)    {        // q is quotient        q = a / m;        t = m;        // m is remainder now, process same as        // Euclid's algo        m = a % m, a = t;        t = x0;        x0 = x1 - q * x0;        x1 = t;    }    // Make x1 positive    if (x1 < 0)       x1 += m0;    return x1;}int POW(int x, int y){    int res= 1;    for ( ; y ; ) {        if ( (y&1) ) {            res*= x;        }        x*=x;        y>>=1;    }    return res;}int inverse(int x){    dd p=((dd)1.0)/x;    return (p)+EPS;}int gcd(int a, int b){    while(b) b^=a^=b^=a%=b;    return a;}int nC2(int n){    return n*(n-1)/2;}ll MOD(ll n,ll mod){    if(n>=0)        return n%mod;    else if(-n==mod)        return 0;    else        return mod+(n%mod);}int n,k,data[20],cnt;vector<int>g[20];set<int>sata;int dfs(int u,int par,int mask){    sata.insert(data[u]);    cnt++;    loop(i,g[u].size())    {        int v=g[u][i];        if(v==par) continue;        if(CHECK(mask,(v-1)))            dfs(v,u,mask);    }}int Subtree(int mask){    int bbit=__builtin_popcount(mask);    for(int i=0;i<n;i++)    {        if(CHECK(mask,i))        {            cnt=0;            sata.clear();            dfs(i+1,0,mask);            int sz=sata.size();            if(cnt==bbit) return sz;            return 0;        }    }    return 0;}int main(){//    freopen("sample_in.txt","r",stdin);//    freopen("sample_out.txt","w",stdout);    int t,cas=0;    getint(t);    assert(t>=1 && t<=15);    while(t--)    {        loop(i,20)        {            g[i].clear();        }        sf("%d %d",&n,&k);        assert(n>=2 && n<=18);        assert(k>=1 && k<=n);        for(int i=1;i<=n;i++)        {            getint(data[i]);            assert(data[i]>=0 && data[i]<=inf);        }        for(int i=0;i<n-1;i++)        {            int a,b;            sf("%d %d",&a,&b);            assert(a>=1 && a<=n);            assert(b>=1 && b<=n);            g[a].pb(b);            g[b].pb(a);        }        int ans=0;        for(int mask=0;mask<(1<<n);mask++)        {            int aa=Subtree(mask);            if(aa==0) continue;            if(aa<=k){                ans++;            }        }        CASE(cas);        pf("%d\n",ans);    }    return  0;}`