# HackerEarth Words And Trees problem solution

In this HackerEarth Words And Trees problem solution You are given a rooted tree with N nodes. Each node contains a lowercase English letter. Node with label 1 is the root.There are Q questions of the form

X S: Here X is the root of subtree and S is a string.

For each question, let T be the string built using all the characters in the nodes of subtree with root X (each subtree node character comes exactly once) .
For each question, print minimum number of characters to be added to T , so that the we can build S using some characters of string T (each character of string T can be used at most once).

## HackerEarth Words And Trees problem solution.

`#include <bits/stdc++.h>using namespace std;#include<limits>#define ll long longtypedef pair<int, int > pii;#define pb push_back#define mk make_pair#define MEM(a,b) memset(a,(b),sizeof(a))#define rep(p,q,r) for(int p=q;p<r;p++)#define repr(p,q,r) for(int p=q;p>=r;p--)#define TEST int test; cin >> test;while(test--)#define si(x) scanf("%d",&x)#define author real_flash#define si2(x,y) scanf("%d %d",&x,&y)#define si3(x,y,z) scanf("%d %d %d",&x,&y,&z)#define sl(x) scanf("%lld",&x)#define prl(x) printf("%lld\n",x)#define ff first#define ss second#define BE(a) a.begin(), a.end()#define bitcnt(x) __builtin_popcountll(x)#define INF 111111111111111LL#define mo 1000000007//std::cout << std::setprecision(3) << std::fixed;int MAX=numeric_limits<int>::max();const int N=1e6+5;//ios_base::sync_with_stdio(0);cin.tie(0);int x,y;int n,q,u,v;int dp[N][26];char ch[N];int mark[N];vector<int> tre[N];void dfs(int s){    mark[s]=1;    rep(i,0,tre[s].size())    {        if(mark[tre[s][i]]==0)        {            dfs(tre[s][i]);        }    }    dp[s][ch[s]-97]++;    rep(i,0,tre[s].size())    {        rep(j,0,26)        {            dp[s][j]+=dp[tre[s][i]][j];        }    }    }int main(){#ifndef ONLINE_JUDGE    freopen("input1.txt", "r", stdin);    freopen("output1.txt", "w", stdout);        #endif    cin>>n>>q;    assert (n<=100000);    rep(i,1,n+1)    {               cin>>ch[i];    }    rep(i,0,n-1)    {        cin>>u>>v;        tre[u].pb(v);        tre[v].pb(u);    }    dfs(1);    while(q--)    {        int x;        string s;        cin>>x>>s;        assert (x<=n);        int siz=s.length();        int arr[26];        MEM(arr,0);        rep(i,0,siz)        {            arr[s[i]-97]++;        }        int f=1;        int ans=0;        rep(i,0,26)        {            //cout<<dp[x][i]<<","<<arr[i]<<" ";            //cout<<(char)(97+i)<<" "<<dp[x][i]<<" "<<arr[i]<<"\n";            if(dp[x][i]<=arr[i])            {                ans+=arr[i]-dp[x][i];            }        }        cout<<ans<<"\n";    }}`

### Second solution

`#include<bits/stdc++.h>using namespace std;char val[100005];bool vis[100005];int n,q,subtree[100005][26];vector<int>v[100005];void dfs(int u){    vis[u]=1;    for(auto c:v[u])    {        if(vis[c])continue;        dfs(c);        for(int i=0;i<26;i++)            subtree[u][i]+=subtree[c][i];    }    subtree[u][val[u]-'a']++;}int main(){    cin>>n;    cin>>q;    for(int i=1;i<=n;i++)        cin>>val[i];    for(int i=1;i<=n-1;i++)    {        int x,y;        cin>>x>>y;        v[x].push_back(y);        v[y].push_back(x);    }    dfs(1);    while(q--)    {        int node;        string s;        cin>>node;        cin>>s;        int f[30]={0};int ans=0;        for(int i=0;i<s.size();i++)            f[s[i]-'a']++;        for(int i=0;i<=25;i++)        {            ans+=max(0,f[i]-subtree[node][i]);        }        cout<<ans<<"\n";    }    return 0;}`