/* */ //#pragma comment(linker, "/STACK:16777216") #include <fstream> #include <iostream> #include <string> #include <complex> #include <math.h> #include <set> #include <vector> #include <map> #include <queue> #include <stdio.h> #include <stack> #include <algorithm> #include <list> #include <ctime> #include <memory.h> #include <ctime> #define y0 sdkfaslhagaklsldk #define y1 aasdfasdfasdf #define yn askfhwqriuperikldjk #define j1 assdgsdgasghsf #define tm sdfjahlfasfh #define lr asgasgash #define eps 1e-9 //#define M_PI 3.141592653589793 #define bs 2717401869ll #define bsize 256 #define right adsgasgadsg #define free adsgasdg #define MAG 10000 using namespace std; string st; long n,m,a,b; vector<long> g[1<<19]; long answ; long ans[1<<10]; long val[1<<20]; long tp,q,s[1<<18][27]; long up[1<<18][20]; long tin[1<<18],tout[1<<18]; long timer; long dep[1<<20]; void dfs(long v,long p) { tin[v]=++timer; s[v][val[v]]++; up[v][0]=p; for (int i=1;i<20;i++) up[v][i]=up[up[v][i-1]][i-1]; for (int i=0;i<g[v].size();i++) { long to=g[v][i]; if (to==p)continue; for (int j=0;j<26;j++) s[to][j]=s[v][j]; dep[to]=dep[v]+1; dfs(to,v); } tout[v]=++timer; } bool upper(long a,long b) { return tin[a]<=tin[b]&&tout[a]>=tout[b]; } long lca(long a,long b) { if (dep[a]<dep[b])swap(a,b); for (int i=19;i+1;--i) { if (dep[a]-(1<<i)>=dep[b]) a=up[a][i]; } for (int i=19;i+1;--i) if (up[a][i]!=up[b][i]) a=up[a][i], b=up[b][i]; if (a==b) return a; return up[a][0]; } int main(){ //freopen("evacuation.in","r",stdin); //freopen("evacuation.out","w",stdout); //freopen("C:/input.txt","r",stdin); //freopen("C:/output.txt","w",stdout); ios_base::sync_with_stdio(0); //cin.tie(0); cin>>n>>m; cin>>st; st="a"+st; for (int i=1;i<n;i++) { cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } for (int i=1;i<=n;i++) val[i]=st[i]-'a'; dfs(1,1); for (;m;--m) { cin>>tp; if (tp==1) { cin>>a>>b; q=lca(a,b); // cout<<q<<endl; for (int i=0;i<26;i++) ans[i]=s[a][i]+s[b][i]-s[q][i]*2; ans[val[q]]++; answ=0; for (int i=0;i<26;i++) if (ans[i]%2) answ++; cout<<answ<<endl; /* for (int i=0;i<26;i++) cout<<ans[i]<<" "; cout<<endl;*/ } else { cin>>a>>st; val[n+1]=st[0]-'a'; up[n+1][0]=a; dep[n+1]=dep[a]+1; for (int i=0;i<26;i++) s[n+1][i]=s[a][i]; s[n+1][val[n+1]]++; for (int i=1;i<20;i++) up[n+1][i]=up[up[n+1][i-1]][i-1]; ++n; } } cin.get();cin.get(); return 0;}