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


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