HackerEarth Words And Trees problem solution YASH PAL, 31 July 2024 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("%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