C++ :

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 30003
#define inf 1000000000
using namespace std;
struct data{
    int l1,l2,r1,r2;
    int d1,d2,d3,d4;
}tr[N*4];
char s[N][3];
int n,m,point[N*2],nxt[N*2],v[N*2],tot,sz;
int belong[N],pos[N],size[N],q[N],son[N],deep[N],fa[N];
void add(int x,int y)
{
    tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; 
    tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x;
}
void dfs(int x,int f)
{
    size[x]=1;
    deep[x]=deep[f]+1;
    for (int i=point[x];i;i=nxt[i]){
        if (v[i]==f) continue;
        fa[v[i]]=x;
        dfs(v[i],x);
        size[x]+=size[v[i]];
        if (size[v[i]]>size[son[x]])
         son[x]=v[i];
    }
}
void dfs1(int x,int chain)
{
    pos[x]=++sz; q[sz]=x; belong[x]=chain;
    if (!son[x]) return;
    dfs1(son[x],chain);
    for (int i=point[x];i;i=nxt[i])
     if(v[i]!=son[x]&&v[i]!=fa[x])
      dfs1(v[i],v[i]);
}
data update(data x,data y)
{
    data a; 
    a.d1=max(x.d1+y.d1,x.d2+y.d3); if (a.d1<0) a.d1=-inf;
    a.d2=max(x.d2+y.d4,x.d1+y.d2); if (a.d2<0) a.d2=-inf;
    a.d3=max(x.d3+y.d1,x.d4+y.d3); if (a.d3<0) a.d3=-inf;
    a.d4=max(x.d3+y.d2,x.d4+y.d4); if (a.d4<0) a.d4=-inf;
    a.l1=x.l1; a.l2=x.l2; a.r1=y.r1; a.r2=y.r2;
    a.l1=max(a.l1,max(x.d1+y.l1,x.d2+y.l2)); if (a.l1<0) a.l1=-inf;
    a.l2=max(a.l2,max(x.d4+y.l2,x.d3+y.l1)); if (a.l2<0) a.l2=-inf;
    a.r1=max(a.r1,max(y.d1+x.r1,y.d3+x.r2)); if (a.r1<0) a.r1=-inf;
    a.r2=max(a.r2,max(y.d2+x.r1,y.d4+x.r2)); if (a.r2<0) a.r2=-inf; 
    return a;
}
void build(int now,int l,int r)
{
    if (l==r) {
        int x=q[l];
        tr[now].d1=tr[now].d2=tr[now].d3=tr[now].d4=-inf;
        tr[now].l1=tr[now].l2=tr[now].r1=tr[now].r2=-inf;
        if (s[x][0]=='.') tr[now].d1=tr[now].l1=tr[now].r1=1;
        if (s[x][1]=='.') tr[now].d4=tr[now].l2=tr[now].r2=1;
        if (s[x][1]=='.'&&s[x][0]=='.')
         tr[now].d2=tr[now].d3=tr[now].l1=tr[now].l2=tr[now].r1=tr[now].r2=2;
        //cout<<tr[now].l1<<" "<<tr[now].l2<<" "<<tr[now].r1<<" "<<tr[now].r2<<endl;
        return;
    }
    int mid=(l+r)/2;
    build(now<<1,l,mid);
    build(now<<1|1,mid+1,r);
    tr[now]=update(tr[now<<1],tr[now<<1|1]);
    //cout<<tr[now].l1<<" "<<tr[now].l2<<" "<<tr[now].r1<<" "<<tr[now].r2<<endl;
}
void pointchange(int now,int l,int r,int pos)
{
    if(l==r) {
        int x=q[l];
        tr[now].d1=tr[now].d2=tr[now].d3=tr[now].d4=-inf;
        tr[now].l1=tr[now].l2=tr[now].r1=tr[now].r2=-inf;
        if (s[x][0]=='.') tr[now].d1=tr[now].l1=tr[now].r1=1;
        if (s[x][1]=='.') tr[now].d4=tr[now].l2=tr[now].r2=1;
        if (s[x][1]=='.'&&s[x][0]=='.')
         tr[now].d2=tr[now].d3=tr[now].l1=tr[now].l2=tr[now].r1=tr[now].r2=2;
        return;
    }
    int mid=(l+r)/2;
    if (pos<=mid) pointchange(now<<1,l,mid,pos);
    else pointchange(now<<1|1,mid+1,r,pos);
    tr[now]=update(tr[now<<1],tr[now<<1|1]);
    //cout<<tr[now].l1<<" "<<tr[now].l2<<" "<<tr[now].r1<<" "<<tr[now].r2<<endl;
}
data query(int now,int l,int r,int ll,int rr)
{
    if (ll<=l&&r<=rr) return tr[now];
    int mid=(l+r)/2;
    if (ll<=mid&&rr>mid) return update(query(now<<1,l,mid,ll,rr),query(now<<1|1,mid+1,r,ll,rr));
    else if (ll<=mid) return query(now<<1,l,mid,ll,rr);
    else return query(now<<1|1,mid+1,r,ll,rr);
}
void clear(data &a)
{
    a.d1=a.d2=a.d3=a.d4=0;
    a.l1=a.l2=a.r1=a.r2=0;
}
int solve(int x,int y)
{
    if (s[x][0]=='#'&&s[x][1]=='#') return 0;
    data a,b; 
    clear(a); clear(b);
    while (belong[x]!=belong[y]) {
        if (deep[belong[x]]>deep[belong[y]]) {
            a=update(query(1,1,n,pos[belong[x]],pos[x]),a);
            x=fa[belong[x]];
        }
        else {
            b=update(query(1,1,n,pos[belong[y]],pos[y]),b);
            y=fa[belong[y]];
        }
    }
    if (deep[x]<deep[y]) b=update(query(1,1,n,pos[x],pos[y]),b);
    else a=update(query(1,1,n,pos[y],pos[x]),a);
    swap(a.l1,a.r1); swap(a.l2,a.r2); swap(a.d2,a.d3);
    a=update(a,b);
    return max(a.l1,a.l2);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<n;i++) {
        int x,y; scanf("%d%d",&x,&y);
        add(x,y);
    }
    dfs(1,0); dfs1(1,1);
    for (int i=1;i<=n;i++) scanf("%s",s[i]);
    build(1,1,n);
    //for (int i=1;i<=n;i++) cout<<pos[i]<<" "; cout<<endl;
    //for (int i=1;i<=n;i++) cout<<q[i]<<" "; cout<<endl;
    //cout<<tr[1].l1<<" "<<tr[1].l2<<" "<<tr[1].r1<<" "<<tr[1].r2<<endl;
    for (int i=1;i<=m;i++) {
        char opt[10];
        int x,y; 
        scanf("%s",opt);
        if (opt[0]=='Q') {
            scanf("%d%d",&x,&y);
            printf("%d\n",solve(x,y));
        }
        else {
            scanf("%d",&x);
            scanf("%s",s[x]);
            pointchange(1,1,n,pos[x]);
        }
    }
}