#include<cstdio> #include<vector> #include<cstring> using namespace std; const int N=100000,SIG=26; void lol(){ int x=0; x++; } class Stram{ public: int v; int lit[SIG+1]; }; Stram st[N+1][20]; class Query{ public: int x,y; Query(){ } Query(int xx,int yy){ x=xx; y=yy; } }; Query q[N+1]; int v[N+1]; int father[N+1]; bool vis[N+1]; int grad[N+1]; char s[N+1]; vector<int>g[N+1]; int nrq; int add; int n,m; void change(int&v1,int&v2){ int aux=v1; v1=v2; v2=aux; } void ssl(int&v1,int&v2,int l){ add=0; if(grad[v1]>grad[v2]) change(v1,v2); if(v[v2]==l) add++; int p=1<<19; int j=19; while(p){ if(grad[v2]-p>=grad[v1]){ add+=st[v2][j].lit[l]; v2=st[v2][j].v; } p/=2; j--; } } int lca(int&v1,int&v2,int l){ ssl(v1,v2,l); int r=add; int p=1<<19; int j=19; if(v1==v2) return r; if(v[v1]==l) r++; while(p){ int anc1=st[v1][j].v; int anc2=st[v2][j].v; if(anc1!=anc2){ r+=st[v1][j].lit[l]; r+=st[v2][j].lit[l]; v1=anc1; v2=anc2; } p/=2; j--; } if(v[father[v1]]==l) r++; return r; } int query(int v1,int v2,int l){ return lca(v1,v2,l); } void set_st(){ for(int i=1;i<=n;i++){ st[i][0].v=father[i]; if(father[i]!=0) st[i][0].lit[v[father[i]]]++; } for(int j=1;1<<j<=n;j<<=1) for(int i=1;i<=n;i++){ st[i][j].v=st[st[i][j-1].v][j-1].v; for(int l=0;l<=SIG;l++) st[i][j].lit[l]+=st[i][j-1].lit[l]+st[st[i][j-1].v][j-1].lit[l]; } } void dfs(int dad){ vis[dad]=true; for(unsigned int i=0;i<g[dad].size();i++){ int son=g[dad][i]; if(!vis[son]){ grad[son]=grad[dad]+1; father[son]=dad; dfs(son); } } } int main(){ //freopen("std.in","r",stdin); //freopen("std.out","w",stdout); scanf("%d%d\n",&n,&m); gets(s); for(int i=1;i<=n;i++) v[i]=s[i-1]-'a'; for(int i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } for(int i=1;i<=m;i++){ int x,y; char z; scanf("%d%d %c",&x,&y,&z); if(x==2){ g[y].push_back(++n); g[n].push_back(y); v[n]=z-'a'; } else q[++nrq]=Query(y,z-'0'); } memset(vis,0,sizeof(vis)); dfs(1); set_st(); for(int i=1;i<=nrq;i++){ int r=0; if(i==nrq-1) lol(); for(int l=0;l<=SIG;l++){ if(l==6) lol(); if(query(q[i].x,q[i].y,l)%2==1) r++; } printf("%d\n",r); } return 0; }