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


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;

}