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 long

typedef 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("%lldn",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;
}

coding problems solutions