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 100005

using 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 operation
int 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;

}