func_code_string: #include <bits/stdc++.h>   using namespace std;   const int L = 500;   const int N = 220000;   const int M1 = 1e9 + 7;   const int M2 = 1e9 + 9;   int chd[N][26], go[N][26];   int len[N], q[N], p[N];   int s[N], dp[N], f[17][N], t[N];   char str[N], _str[N];   int st[N], en[N], wh[N], fr[N], to[N], cur[N], state[N], id[N], ans[N], cnt[N],       sum[N], chk[N], a[N], b[N];   int h1[N], h2[N], hh1[N], hh2[N], hs1[N], hs2[N], p1[N], p2[N];   vector<int> adj[N], con[N];   int sn, e[N];   char w[N], ch[N];   void dfs(int u, int p) {     s[u] = sn;     f[0][u] = p;     dp[u] = dp[p] + 1;     for (int i = 1; i < 17; i++) f[i][u] = f[i - 1][f[i - 1][u]];     for (int tt : adj[u]) {       int v = e[tt] ^ u;       if (v == p) continue;       ch[v] = w[tt];       a[sn] = u, b[sn] = v;       t[sn++] = tt;       dfs(v, u);       a[sn] = v, b[sn] = u;       t[sn++] = tt;     }   }   int T;   void dfs(int u) {     st[u] = ++T;     for (int v : con[u]) {       dfs(v);     }     en[u] = T;   }   void modify(int x, int y) {     cnt[x] += y;     sum[x / L] += y;   }   int query(int l, int r) {     int ll = l / L, rr = r / L;     int ret = 0;     if (ll == rr) {       for (int i = l; i <= r; i++) ret += cnt[i];       return ret;     }     for (int i = l; i < min((ll + 1) * L, r + 1); i++) ret += cnt[i];     for (int i = max(l, rr * L); i <= r; i++) ret += cnt[i];     for (int i = ll + 1; i < rr; i++) ret += sum[i];     return ret;   }   int lca(int u, int v) {     if (dp[u] < dp[v]) swap(u, v);     for (int d = dp[u] - dp[v], i = 0; i < 17; i++)       if (d >> i & 1) u = f[i][u];     if (u == v) return u;     for (int i = 16; i >= 0; i--) {       if (f[i][u] == f[i][v]) continue;       u = f[i][u], v = f[i][v];     }     return f[0][u];   }   int n, m, Q;   const int B1 = 31;   const int B2 = 47;   pair<int, int> get(int *h1, int *h2, int l, int s, int e) {     return make_pair((h1[e + 1] + 1LL * (M1 - h1[s]) * p1[e - s + 1]) % M1,                      (h2[e + 1] + 1LL * (M2 - h2[s]) * p2[e - s + 1]) % M2);   }   int make_path(int u, int v) {     int p = lca(u, v);     int ret = 0;     while (u != p) {       _str[ret++] = ch[u];       u = f[0][u];     }     int nret = ret;     while (v != p) {       _str[ret++] = ch[v];       v = f[0][v];     }     reverse(_str + nret, _str + ret);     for (int i = 0; i < ret; i++) {       hh1[i + 1] = (1LL * hh1[i] * B1 + _str[i] -  a ) % M1;       hh2[i + 1] = (1LL * hh2[i] * B2 + _str[i] -  a ) % M2;     }     return ret;   }   int dist(int u, int v) { return dp[u] + dp[v] - 2 * dp[lca(u, v)]; }   int main() {     scanf( %d%d%d , &n, &m, &Q);     for (int i = 1; i < n; i++) {       int u, v;       char c[3];       scanf( %d%d%s , &u, &v, c);       e[i] = u ^ v;       w[i] = c[0];       adj[u].push_back(i);       adj[v].push_back(i);     }     dfs(1, 0);     int nodes = 1;     for (int i = 0; i < N; i++)       p1[i] = (i == 0 ? 1 : 1LL * p1[i - 1] * B1 % M1),       p2[i] = (i == 0 ? 1 : 1LL * p2[i - 1] * B2 % M2);     for (int i = 1; i <= m; i++) {       scanf( %s , str);       int l = strlen(str);       for (int k = 0; k < 2; k++) {         int u = 1, ret1 = 0, ret2 = 0;         for (int j = 0; str[j]; j++) {           int c = str[j] -  a ;           ret1 = (1LL * ret1 * B1 + c) % M1, ret2 = (1LL * ret2 * B2 + c) % M2;           int &v = chd[u][c];           if (!v) v = ++nodes;           u = v;         }         hs1[k * m + i] = ret1;         hs2[k * m + i] = ret2;         state[k * m + i] = u;         reverse(str, str + l);       }       len[i] = len[i + m] = l;     }     int qn = 0;     for (int i = 0, u; i < 26; i++)       if (u = chd[1][i]) q[qn++] = u, p[u] = 1;     for (int i = 0; i < qn; i++) {       int u = q[i];       for (int j = 0, v; j < 26; j++)         if (v = chd[u][j]) {           int w = p[u];           while (w > 1 && !chd[w][j]) w = p[w];           w = max(1, chd[w][j]);           p[v] = w;           q[qn++] = v;         }     }     for (int i = 0; i < 26; i++) go[1][i] = max(1, chd[1][i]);     for (int i = 0; i < qn; i++) {       int u = q[i];       for (int j = 0; j < 26; j++) {         if (chd[u][j])           go[u][j] = chd[u][j];         else           go[u][j] = go[p[u]][j];       }     }     for (int i = 2; i <= nodes; i++) con[p[i]].push_back(i);     dfs(1);     for (int i = 1; i <= Q; i++) {       scanf( %d%d%d , &fr[i], &to[i], &wh[i]);       if (s[fr[i]] > s[to[i]]) {         swap(fr[i], to[i]);         wh[i] += m;       }       fr[i] = s[fr[i]];       to[i] = s[to[i]] - 1;       id[i] = i;     }     sort(id + 1, id + Q + 1, [](int i, int j) {       if (fr[i] / L != fr[j] / L) return fr[i] / L < fr[j] / L;       return to[i] < to[j];     });     for (int i = 1, j; i <= Q; i = j) {       int u = id[i];       int r = fr[u] / L * L - 1;       memset(chk, 0, sizeof chk);       memset(cnt, 0, sizeof cnt);       memset(sum, 0, sizeof sum);       int rn = 0;       cur[0] = 1;       for (j = i; j <= Q && fr[id[i]] / L == fr[id[j]] / L; j++) {         int v = id[j];         while (r < to[v]) {           ++r;           int eid = t[r];           int c = w[eid] -  a ;           if (chk[eid]) {             modify(st[cur[rn]], -1);             rn--;           } else {             cur[rn + 1] = go[cur[rn]][c];             h1[rn + 1] = (1LL * h1[rn] * B1 + c) % M1;             h2[rn + 1] = (1LL * h2[rn] * B2 + c) % M2;             modify(st[cur[++rn]], 1);           }           chk[eid] ^= 1;         }         int who = wh[v];         ans[v] = query(st[state[who]], en[state[who]]);         int xx = a[fr[u] / L * L];         int yy = a[fr[v]];         int zz = b[r];         int pxy = lca(xx, yy);         int pyz = lca(yy, zz);         int pzx = lca(zz, xx);         int pp = pxy ^ pyz ^ pzx;         int xy = dp[xx] + dp[yy] - 2 * dp[pxy];         int yz = dp[zz] + dp[yy] - 2 * dp[pyz];         int zx = dp[xx] + dp[zz] - 2 * dp[pzx];         int xlen = (xy + zx - yz) / 2;         assert(xlen == dist(xx, pp));         assert(rn == zx);         int _ans = ans[v];         for (int k = 0; k < xlen; k++) {           if (k + len[who] - 1 >= rn) break;           auto ret = get(h1, h2, rn, k, k + len[who] - 1);           if (ret.first == hs1[who] && ret.second == hs2[who]) ans[v]--;         }         int __ans = ans[v];         int ylen = make_path(yy, pp);         for (int k = 0; k < ylen; k++) {           if (k + len[who] - 1 < ylen) {             auto ret = get(hh1, hh2, ylen, k, k + len[who] - 1);             if (ret.first == hs1[who] && ret.second == hs2[who]) ans[v]++;             continue;           }           if (len[who] - ylen + k > rn - xlen) break;           auto first = get(hh1, hh2, ylen, k, ylen - 1);           auto second = get(h1, h2, rn, xlen, xlen + len[who] - (ylen - k) - 1);           int ret1 =               (1LL * first.first * p1[len[who] - (ylen - k)] + second.first) % M1;           int ret2 =               (1LL * first.second * p2[len[who] - (ylen - k)] + second.second) %               M2;           if (ret1 == hs1[who] && ret2 == hs2[who]) ans[v]++;         }       }     }     for (int i = 1; i <= Q; i++) printf( %d n , ans[i]);     return 0;   }   