3.10s

对每条重链单独建线段树，可以证明跳链的时候有 $\mathcal{O}(\log n)$ 次查询时间复杂度为 $\mathcal{O}(1)$，$\mathcal{O}(1)$ 次查询时间复杂度为 $\mathcal{O}(\log n)$。

// author: lzyqwq
#include <bits/stdc++.h>
#define int long long
#define eb emplace_back
#define str string
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)
#define mst memset
#define sof sizeof
using namespace std; const int N = 1e5 + 5; vector<int> g[N]; str s[N];
int n, m, d[N], t[N], h[N], f[N], sz[N], dfn[N], cnt, ed[N], id[N];
void init_main() {

}
void qingkong() {

}
void dfs1(int u) {
    sz[u] = 1;
    for (int v : g[u]) {
        if (v == f[u]) continue; d[v] = d[f[v] = u] + 1; 
        dfs1(v); sz[u] += sz[v]; if (sz[v] > sz[h[u]]) h[u] = v;
    }
}
void dfs2(int u) {
    dfn[u] = ++cnt; id[cnt] = u;
    if (h[u]) t[h[u]] = t[u], dfs2(h[u]); else ed[t[u]] = cnt;
    for (int v : g[u]) {
        if (v == f[u] || v == h[u]) continue; t[v] = v; dfs2(v);
    }
}
struct node { 
    int f[2][2], g[2][2]; str l, r; bool e, okl[2][2], okr[2][2]; 
    node(str l_ = "", str r_ = "", bool e_ = 1) {
        l = l_; r = r_; e = e_; mst(f, 0, sof f); mst(g, 0, sof g); 
        mst(okl, 0, sof okl); mst(okr, 0, sof okr);
    }
    node operator+(const node &o) const {
        if (e) return o; if (o.e) return *this; node ret;
        ret.l = l; ret.r = o.r; ret.e = 0;
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j) 
                for (int k = 0; k < 2; ++k) {
                    bool op = (r[k] == '.' && o.l[k] == '.' && okl[i][k]);
                    ret.okl[i][j] |= (op & o.okl[k][j]);
                    ret.f[i][j] = max(ret.f[i][j], f[i][k] + op * o.f[k][j]),
                    op = (r[k] == '.' && o.l[k] == '.' && o.okr[i][k]);
                    ret.okr[i][j] |= (op & okr[k][j]);
                    ret.g[i][j] = max(ret.g[i][j], o.g[i][k] + op * g[k][j]);
                }
        return ret;
    }
};
struct SegmentTree {
    vector<node> S; int L, R;
    void upd(node &o, str s) {
        o = node(s, s, 0);
        for (int i = 0; i < 2; ++i) 
            if (s[i] == '.') 
                o.f[i][i] = o.g[i][i] = o.okl[i][i] = o.okr[i][i] = 1;
        if (s[0] =='.' && s[1] == '.') 
            o.f[0][1] = o.f[1][0] = o.g[0][1] = o.g[1][0] = 2,
            o.okl[0][1] = o.okl[1][0] = o.okr[0][1] = o.okr[1][0] = 1;
    }
    void build(int x, int l, int r) {
        if (l == r) return void(upd(S[x], s[id[l]]));
        int mid = (l + r) >> 1; build(ls(x), l, mid);
        build(rs(x), mid + 1, r); S[x] = S[ls(x)] + S[rs(x)];
    }
    void init(int l, int r) {
        S.resize((r - l + 1) << 2); build(1, L = l, R = r);
    }
    void mdf(int x, int l, int r, int k, str s) {
        if (l == r) return void(upd(S[x], s)); int mid = (l + r) >> 1;
        if (k <= mid) mdf(ls(x), l, mid, k, s); else mdf(rs(x), mid + 1, r, k, s);
        S[x] = S[ls(x)] + S[rs(x)];
    }
    node qry(int x, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return S[x]; int mid = (l + r) >> 1; node ret;
        if (ql <= mid) ret = qry(ls(x), l, mid, ql, qr);
        if (qr > mid) ret = ret + qry(rs(x), mid + 1, r, ql, qr); return ret;
    }
} T[N];
node qry(int x, int y) {
    node rx, ry;
    while (t[x] != t[y]) 
        if (d[t[x]] > d[t[y]]) {
            rx = T[t[x]].qry(1, T[t[x]].L, T[t[x]].R, dfn[t[x]], dfn[x]) + rx;
            x = f[t[x]];
        } else {
            ry = T[t[y]].qry(1, T[t[y]].L, T[t[y]].R, dfn[t[y]], dfn[y]) + ry;
            y = f[t[y]];
        }
    if (d[x] < d[y]) 
        ry = T[t[x]].qry(1, T[t[x]].L, T[t[x]].R, dfn[x], dfn[y]) + ry;
    else 
        rx = T[t[x]].qry(1, T[t[x]].L, T[t[x]].R, dfn[y], dfn[x]) + rx;
    swap(rx.f, rx.g); swap(rx.l, rx.r); swap(rx.okl, rx.okr); return rx + ry;
}
void work() {
    qingkong(); cin >> n >> m;
    for (int i = 1, u, v; i < n; ++i) cin >> u >> v, g[u].eb(v), g[v].eb(u);
    for (int i = 1; i <= n; ++i) cin >> s[i]; dfs1(1); dfs2(t[1] = 1);
    for (int i = 1; i <= n; ++i) if (t[i] == i) T[i].init(dfn[i], ed[i]);
    for (int i = 1, u, v; i <= m; ++i) {
        char op; str s; cin >> op >> u;
        if (op == 'Q') {
            cin >> v; int ans = 0; node tmp = qry(u, v);
            if (tmp.l == "##") { cout << "0\n"; continue; }
            for (int x = 0; x < 2; ++x) 
                for (int y = 0; y < 2; ++y) ans = max(ans, tmp.f[x][y]);
            cout << ans << '\n';
        } else cin >> s, T[t[u]].mdf(1, T[t[u]].L, T[t[u]].R, dfn[u], s);
    }
}
signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    init_main(); int testcases = 1;
    // cin >> testcases;
    // read(testcases);
    while (testcases--) work(); return 0;
}