#include <iostream> #include <string> #include <vector> #include <fstream> #include <bitset> using namespace std; vector<int> V[100001]; char letter[100001]; int t[100001]; int euler[3*100001]; int nivel[3*100001]; int frec[100001][28]; bitset<100001> used; vector<pair<int, int> >op; int auxn; int rmq[3*100001][24]; int log[3*100001]; int f[3*100001]; void create_euler(int nod,int niv) { euler[++auxn] = nod; f[nod] = auxn; nivel[auxn] = niv; frec[nod][letter[nod]-'a']++; used[nod] = true; for(vector<int>::iterator it = V[nod].begin(); it != V[nod].end(); it++) if(!used[*it]) { for(int i = 0; i <= 26; i++) frec[*it][i]+=frec[nod][i]; t[*it] = nod; create_euler(*it,niv+1); euler[++auxn] = nod; nivel[auxn] = niv; } } int LCA(int x, int y) { x = f[x],y = f[y]; if(x > y) swap(x,y); int l = log[y-x+1]; if(nivel[rmq[x][l]] < nivel[rmq[y - (1<<l)+1][l]]) return euler[rmq[x][l]]; else return euler[rmq[y-(1<<l)+1][l]]; } void afis(int x, int y) { int sol = 0; int L = LCA(x,y); int j = 0; //cout<<x<<' '<<y<<" "; while(j <= 26) { if(((frec[x][j] + frec[y][j] - frec[L][j] - frec[t[L]][j]) & 1) == 1) { sol++; //cout<<(char)(j+'a'); } j++; } cout<<sol<<'\n'; } int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); int n,m; used.reset(); cin>>n>>m; for(int i = 1; i <= n; i++) { cin>>letter[i]; } int a,b,x; for(int i = 1; i < n; i++) { cin>>a>>b; V[a].push_back(b); V[b].push_back(a); } char c; for(int i = 1; i <= m; i++) { cin>>x; if(x == 1) { cin>>a>>b; op.push_back(make_pair(a,b)); } else { cin>>a>>c; V[a].push_back(++n); V[n].push_back(a); letter[n] = c; } } create_euler(1,0); int nn = n; n = auxn; for(int i=1;i<=n;i++) { rmq[i][0] = i; if(i>1) log[i] = 1+log[i>>1]; } for(int j=1;(1<<j)<=n;j++) for(int i=1;i+(1<<j)-1<=n;i++) if(nivel[ rmq[i][j-1] ] < nivel[ rmq[i + (1<<(j-1)) ][j-1] ]) rmq[i][j] = rmq[i][j-1]; else rmq[i][j] = rmq[i + (1<<(j-1))][j-1]; for(vector<pair<int, int> >::iterator it = op.begin(); it != op.end(); it++) { int x = it->first; int y = it->second; afis(x, y); } /* for(int i = 1; i <=n ;i ++) { for(int j =0;j<=26;j++) cout<<frec[i][j]<<' '; cout<<'\n'; }*/ return 0; }