func_code_string: #include <bits/stdc++.h>   using namespace std;   using namespace std;   int M1(int x) { return x >= 1000000007 ? x - 1000000007 : x; }   int M2(int x) { return x >= 1000000009 ? x - 1000000009 : x; }   struct Hash {     int a, b;     Hash() { a = b = 0; }     Hash(int a, int b) : a(a), b(b) {}     Hash(int a) : a(a), b(a) {}     bool operator<(const Hash& h) const { return a == h.a ? b < h.b : a < h.a; }     bool operator!=(const Hash& h) const { return a != h.a || b != h.b; }     bool operator==(const Hash& h) const { return a == h.a && b == h.b; }     Hash operator+(const Hash& h) const { return Hash(M1(a + h.a), M2(b + h.b)); }     Hash operator-(const Hash& h) const {       return Hash(M1(a - h.a + 1000000007), M2(b - h.b + 1000000009));     }     Hash operator*(const Hash& h) const {       return Hash(((long long)a * h.a) % 1000000007,                   ((long long)b * h.b) % 1000000009);     }     Hash inv() const { return Hash(M1(1000000007 - a), M2(1000000009 - b)); }   };   struct Hash_map {     Hash v[11009989 + 1];     int val[11009989 + 1], head[11009989 + 1], nxt[11009989 + 1], ptr;     void clear() { ptr = 0; }     void insert(Hash a) {       int x = (19260817ll * a.a + a.b) % 11009989;       for (int y = head[x]; y; y = nxt[y])         if (v[y] == a) return;       v[++ptr] = a, nxt[ptr] = head[x], head[x] = ptr;     }     int count(Hash a) {       int x = (19260817ll * a.a + a.b) % 11009989;       for (int y = head[x]; y; y = nxt[y])         if (v[y] == a) return true;       return false;     }     int& operator[](Hash a) {       int x = (19260817ll * a.a + a.b) % 11009989;       for (int y = head[x]; y; y = nxt[y])         if (v[y] == a) return val[y];       v[++ptr] = a, nxt[ptr] = head[x], head[x] = ptr;       return val[ptr];     }   } st;   Hash pw[100100], _pw[100100];   struct Data {     int len, id;     Hash h;   };   int anses[100100], prec[100100], dep[100100], fa[21][100100], n, m;   vector<pair<int, int> > G[100100];   vector<Data> Q[100100];   void dfs(int u, int f) {     fa[0][u] = f;     for (auto c : G[u])       if (c.first != f) {         dep[c.first] = dep[u] + 1;         pw[c.first] = pw[u] * Hash(19260817, 20010911) + Hash(c.second, c.second);         prec[c.first] = c.second;         dfs(c.first, u);       }   }   Hash get(int l, int r) { return pw[l] - pw[r] * _pw[dep[l] - dep[r]]; }   int lca(int u, int v) {     if (dep[u] < dep[v]) swap(u, v);     int d = dep[u] - dep[v];     for (int i = 0; d >> i; i++)       if (d >> i & 1) u = fa[i][u];     if (u == v) return u;     for (int i = 19; i >= 0; --i)       if (fa[i][u] ^ fa[i][v]) u = fa[i][u], v = fa[i][v];     return fa[0][u];   }   int jmp(int u, int d) {     for (int i = 0; d >> i; i++)       if (d >> i & 1) u = fa[i][u];     return u;   }   Hash geth(char* s) {     Hash ret = 0;     for (int i = 0; s[i]; i++) ret = ret * Hash(19260817, 20010911) + (s[i]);     return ret;   }   int kmp(char* t, char* s) {     static int f[100100];     int ns = strlen(s);     for (int i = 0; i < ns; ++i) f[i] = 0;     f[0] = -1;     for (int i = 1; s[i]; i++) {       int j = f[i - 1];       while (j != -1 && s[j + 1] != s[i]) j = f[j];       if (s[j + 1] == s[i]) j++;       f[i] = j;     }     int ans = 0;     for (int i = 0, x = -1; t[i]; i++) {       while (x != -1 && s[x + 1] != t[i]) x = f[x];       if (s[x + 1] == t[i]) x++;       if (x == ns - 1) ans++;     }     return ans;   }   void dfs2(int u, int f) {     for (int i = 1, x = f; i <= 100 && x; i++) {       st[get(u, x)]++;       x = fa[0][x];     }     for (auto c : Q[u]) {       anses[abs(c.id)] += (c.id > 0 ? 1 : -1) * st[c.h];     }     for (auto c : G[u])       if (c.first != f) dfs2(c.first, u);     for (int i = 1, x = f; i <= 100 && x; i++) st[get(u, x)]--, x = fa[0][x];   }   int main() {     scanf( %d , &n);     _pw[0] = Hash(1, 1);     for (int i = 1; i <= n; ++i) _pw[i] = _pw[i - 1] * Hash(19260817, 20010911);     for (int i = 2, u, v; i <= n; ++i) {       char s[2];       scanf( %d%d%s , &u, &v, s);       G[u].push_back(pair<int, int>(v, s[0]));       G[v].push_back(pair<int, int>(u, s[0]));     }     dfs(1, 0);     for (int i = 1; i < 20; ++i)       for (int j = 1; j <= n; ++j) fa[i][j] = fa[i - 1][fa[i - 1][j]];     scanf( %d , &m);     for (int i = 1, u, v; i <= m; ++i) {       char s[200], t[300];       int tp = 0;       scanf( %d%d%s , &u, &v, s);       int lc = lca(u, v), len = strlen(s);       int zu = jmp(u, max(0, dep[u] - dep[lc] - len));       int zv = jmp(v, max(0, dep[v] - dep[lc] - len));       Q[zv].push_back(Data{len, -i, geth(s)});       Q[v].push_back(Data{len, i, geth(s)});       reverse(s, s + len);       Q[zu].push_back(Data{len, -i, geth(s)});       Q[u].push_back(Data{len, i, geth(s)});       reverse(s, s + len);       while (zu != lc) t[tp++] = prec[zu], zu = fa[0][zu];       int xp = tp;       while (zv != lc) t[tp++] = prec[zv], zv = fa[0][zv];       reverse(t + xp, t + tp);       t[tp] = 0;       anses[i] = kmp(t, s);     }     dfs2(1, 0);     for (int i = 1; i <= m; ++i) printf( %d n , anses[i]);   }   