func_code_string: #include <bits/stdc++.h>   namespace _ {   const int inf = 1e9 + 7;   namespace _in {   template <class T>   inline T read() {     char ch;     bool flag = 0;     T x = 0;     while (ch = getchar(), !isdigit(ch))       if (ch ==  - ) flag = 1;     while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();     return flag ? -x : x;   }   struct {     inline operator long long() { return read<long long>(); }     inline operator int() { return read<int>(); }     inline operator bool() { return read<bool>(); }     template <class T>     inline void operator()(T &x) {       x = *this;     }     template <class T, class... A>     inline void operator()(T &x, A &...a) {       x = *this, this->operator()(a...);     }   } IN;   }  // namespace _in   using namespace _in;   namespace _std {   template <class T>   inline void swap(T &x, T &y) {     x ^= y ^= x ^= y;   }   template <class T>   inline T max(T x, T y) {     if (x < y) x = y;     return x;   }   template <class T>   inline T min(T x, T y) {     if (x > y) x = y;     return x;   }   template <class T>   inline void chkmax(T &x, T y) {     if (x < y) x = y;   }   template <class T>   inline void chkmin(T &x, T y) {     if (x > y) x = y;   }   }  // namespace _std   using namespace _std;   }  // namespace _   using namespace _;   const int N = 1e5 + 2;   const int LogN = 18;   struct Edge_Node {     int to, val;   };   struct Query {     int id1, id2, typ, val;   };   char tmp_str[N];   int n, m, q, ans[N], fa_ch[N], len_str[N];   int *str[N];   std::vector<Edge_Node> son[N];   std::vector<Query> que_nod[N];   namespace Hash {   const std::pair<unsigned int, unsigned int> base =       std::pair<unsigned int, unsigned int>(7, 23);   inline std::pair<unsigned int, unsigned int> operator+(       const std::pair<unsigned int, unsigned int> &a,       const std::pair<unsigned int, unsigned int> &b) {     return std::pair<unsigned int, unsigned int>(a.first + b.first,                                                  a.second + b.second);   }   inline std::pair<unsigned int, unsigned int> operator-(       const std::pair<unsigned int, unsigned int> &a,       const std::pair<unsigned int, unsigned int> &b) {     return std::pair<unsigned int, unsigned int>(a.first - b.first,                                                  a.second - b.second);   }   inline std::pair<unsigned int, unsigned int> operator*(       const std::pair<unsigned int, unsigned int> &a,       const std::pair<unsigned int, unsigned int> &b) {     return std::pair<unsigned int, unsigned int>(a.first * b.first,                                                  a.second * b.second);   }   inline bool operator==(const std::pair<unsigned int, unsigned int> &a,                          const std::pair<unsigned int, unsigned int> &b) {     return (a.first == b.first) && (a.second == b.second);   }   }  // namespace Hash   using namespace Hash;   struct BIT {     int lim, res, c[N];     inline int lowbit(int x) { return x & (-x); }     inline void update(int x, int y) {       for (; x <= lim; x += lowbit(x)) c[x] += y;     }     inline int _sum(int x) {       res = 0;       for (; x; x -= lowbit(x)) res += c[x];       return res;     }     inline int query(int l, int r) { return _sum(r) - _sum(l - 1); }   } bit[2];   struct AC_AutoMaton {     std::queue<int> que;     std::vector<int> son[N];     int tot, tim, ch[N][26], fail[N], pos[N], dfn[N], siz[N];     inline void build() {       for (int i = 0; i < 26; ++i)         if (ch[0][i]) fail[ch[0][i]] = 0, que.push(ch[0][i]);       while (!que.empty()) {         int u = que.front();         que.pop();         for (int c = 0; c < 26; ++c)           if (ch[u][c])             fail[ch[u][c]] = ch[fail[u]][c], que.push(ch[u][c]);           else             ch[u][c] = ch[fail[u]][c];       }     }     inline void insert(int id) {       int now = 0, len = len_str[id];       for (int i = 1; i <= len; ++i) {         if (!ch[now][str[id][i]]) ch[now][str[id][i]] = ++tot;         now = ch[now][str[id][i]];       }       pos[id] = now;     }     void get_son() {       for (int i = 1; i <= tot; ++i) son[fail[i]].push_back(i);     }     void pre_dfn(int u) {       dfn[u] = ++tim, siz[u] = 1;       for (int v : son[u]) pre_dfn(v), siz[u] += siz[v];     }   } acm[2];   namespace LCA {   int dep[N], fa[N][LogN];   void get_fa(int u, int f) {     fa[u][0] = f, dep[u] = dep[f] + 1;     for (int i = 1; i < 18; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];     for (Edge_Node now : son[u])       if (now.to != f) get_fa(now.to, u), fa_ch[now.to] = now.val;   }   inline int Lca(int x, int y) {     if (x == y) return x;     if (dep[x] < dep[y]) swap(x, y);     for (int i = 17; ~i; --i)       if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];     if (x == y) return x;     for (int i = 17; ~i; --i)       if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];     return fa[x][0];   }   inline int kth(int x, int d) {     if (dep[x] < d) return -1;     for (int i = 17; ~i; --i)       if (dep[fa[x][i]] >= d) x = fa[x][i];     return x;   }   }  // namespace LCA   using namespace LCA;   std::pair<unsigned int, unsigned int> sum[N], has_pow[N];   inline std::pair<unsigned int, unsigned int> tree_calc(int x, int y) {     return sum[x] - sum[y] * has_pow[dep[x] - dep[y]];   }   int tot_bor[2];   struct Border {     int s, t, d;   } border[N][2];   struct KMP {     int n, *las, *nxt, *del;     inline void build(int id) {       n = len_str[id], nxt = new int[(n + 2)](), las = new int[(n + 2)](),       del = new int[(n + 2)]();       del[1] = las[1] = 1;       for (int i = 2, t = 0; i <= n; ++i) {         while (t && str[id][i] != str[id][t + 1]) t = nxt[t];         if (str[id][i] == str[id][t + 1]) ++t;         nxt[i] = t, del[i] = i - t, las[i] = (del[i] == del[t]) ? las[t] : i;       }     }     inline void get_border(int pos, int len, int typ) {       while (pos > len) pos = nxt[pos];       while (pos > 0) {         border[++tot_bor[typ]][typ] = (Border){las[pos], pos, del[pos]};         pos = nxt[las[pos]];       }     }   } kmp[N][2];   int hep[N];   struct Suffix_Array {     std::pair<unsigned int, unsigned int> *has;     int n, m, *x, *y, *sa, *ch;     inline std::pair<unsigned int, unsigned int> sa_calc(int l, int r) {       return has[r] - has[l - 1] * has_pow[r - l + 1];     }     inline void sort() {       for (int i = 0; i <= m; ++i) hep[i] = 0;       for (int i = 1; i <= n; ++i) ++hep[x[i]];       for (int i = 1; i <= m; ++i) hep[i] += hep[i - 1];       for (int i = n; i >= 1; --i) sa[hep[x[y[i]]]--] = y[i];     }     inline void build(int id) {       n = len_str[id], m = 27;       x = new int[(n + 2)](), y = new int[(n + 2)](), sa = new int[(n + 2)](),       ch = new int[(n + 2)]();       has = new std::pair<unsigned int, unsigned int>[(n + 2)]();       has[0] = std::pair<unsigned int, unsigned int>(1, 1);       for (int i = 1; i <= n; ++i)         has[i] = has[i - 1] * base +                  std::pair<unsigned int, unsigned int>(str[id][i], str[id][i]);       for (int i = 1; i <= n; ++i)         x[y[i] = i] = str[id][i] + 1, ch[i] = str[id][i];       sort();       for (int w = 1, p = 0; m = p, p < n; w <<= 1) {         for (int i = 1; i <= w; ++i) y[p = i] = n - w + i;         for (int i = 1; i <= n; ++i)           if (sa[i] > w) y[++p] = sa[i] - w;         sort(), std::swap(x, y), x[sa[1]] = p = 1;         for (int i = 2; i <= n; ++i)           x[sa[i]] =               (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + w] == y[sa[i - 1] + w])                   ? p                   : ++p;       }     }     inline int lcp(int p, int u, int lca, int len = 0) {       if (u == lca) return 0;       p = sa[p], len = n - p + 1;       if (len >= dep[u] - dep[lca] &&           tree_calc(u, lca) == sa_calc(p, p + dep[u] - dep[lca] - 1))         return dep[u] - dep[lca];       else {         int las;         for (int i = 17; ~i; --i)           if (dep[u] - dep[lca] > (1 << i)) {             las = u, u = fa[u][i];             if (len >= dep[u] - dep[lca] &&                 tree_calc(u, lca) == sa_calc(p, p + dep[u] - dep[lca] - 1))               u = las;           }         u = fa[u][0];         return dep[u] - dep[lca];       }     }     inline bool check(int mid, int u, int lca) {       int now = lcp(mid, u, lca);       if (now == n - sa[mid] + 1) return true;       if (now == dep[u] - dep[lca]) return false;       return ch[sa[mid] + now] < fa_ch[kth(u, dep[lca] + now + 1)];     }     inline void get_maxlen(int u, int lca, int id, int typ) {       int l = 1, r = n, mid, ans = 0;       while (l <= r)         check(mid = (l + r) >> 1, u, lca) ? ans = mid, l = mid + 1 : r = mid - 1;       if (!ans) return;       int len = lcp(ans, u, lca), pos = n - sa[ans] + 1;       kmp[id][typ].get_border(pos, len, typ);     }   } sa[N][2];   inline void addedge(int u = 0, int v = 0) {     IN(u, v), scanf( %s , tmp_str);     son[u].push_back((Edge_Node){v, tmp_str[0] -  a }),         son[v].push_back((Edge_Node){u, tmp_str[0] -  a });   }   void get_ac_ans(int u, int t1, int t2) {     bit[0].update(acm[0].dfn[t1], 1);     bit[1].update(acm[1].dfn[t2], 1);     for (Query now : que_nod[u]) {       int id = now.id2, p = now.typ, v = now.val, k = acm[p].pos[now.id1];       ans[id] +=           v * bit[p].query(acm[p].dfn[k], acm[p].dfn[k] + acm[p].siz[k] - 1);     }     for (Edge_Node now : son[u]) {       int v = now.to, c = now.val;       if (v == fa[u][0]) continue;       get_ac_ans(v, acm[0].ch[t1][c], acm[1].ch[t2][c]);     }     bit[0].update(acm[0].dfn[t1], -1);     bit[1].update(acm[1].dfn[t2], -1);   }   void get_hash(int u) {     for (Edge_Node now : son[u]) {       int v = now.to, c = now.val;       if (v == fa[u][0]) continue;       sum[v] = sum[u] * base + std::pair<unsigned int, unsigned int>(c, c),       get_hash(v);     }   }   inline int exgcd(int a, int b, int &x, int &y) {     if (!b) return x = 1, y = 0, a;     int t = exgcd(b, a % b, y, x);     return y -= a / b * x, t;   }   inline int get_ans(int a, int b, int la, int lb, int c) {     int x, y, gcd = exgcd(a, b, x, y);     if (c % gcd) return 0;     x *= c / gcd, y *= c / gcd;     int _a = a / gcd, _b = b / gcd, _x = (x % _b + _b) % _b;     y += ((x - _x) / _b) * _a, x = _x;     if (y < 0) return 0;     if (y > lb) {       int t = (y - lb - 1) / _a + 1;       y -= t * _a, x += t * _b;     }     if (x < 0 || y < 0 || x > la || y > lb) return 0;     return min((la - x) / _b + 1, y / _a + 1);   }   inline int kmp_solve(int u, int v, int lca, int id) {     tot_bor[0] = tot_bor[1] = 0;     sa[id][1].get_maxlen(u, lca, id, 0);     sa[id][0].get_maxlen(v, lca, id, 1);     int res = 0;     for (int i = 1; i <= tot_bor[0]; ++i)       for (int j = 1; j <= tot_bor[1]; ++j)         if (border[i][0].s + border[j][1].s <= len_str[id] &&             border[i][0].t + border[j][1].t >= len_str[id]) {           int la = (border[i][0].t - border[i][0].s) / border[i][0].d;           int lb = (border[j][1].t - border[j][1].s) / border[j][1].d;           res += get_ans(border[i][0].d, border[j][1].d, la, lb,                          len_str[id] - border[i][0].s - border[j][1].s);         }     return res;   }   int u, v, id;   int main() {     IN(n, m, q);     for (int i = 2; i <= n; ++i) addedge();     get_fa(1, 0), get_hash(1);     has_pow[0] = std::pair<unsigned int, unsigned int>(1, 1);     for (int i = 1; i < N; ++i) has_pow[i] = has_pow[i - 1] * base;     for (int i = 1; i <= m; ++i) {       scanf( %s , tmp_str), len_str[i] = strlen(tmp_str);       str[i] = new int[len_str[i] + 2]();       for (int j = 1; j <= len_str[i]; ++j) str[i][j] = tmp_str[j - 1] -  a ;       str[i][0] = str[i][len_str[i] + 1] = -1;       acm[0].insert(i);       sa[i][0].build(i);       kmp[i][0].build(i);       std::reverse(str[i] + 1, str[i] + 1 + len_str[i]);       acm[1].insert(i);       sa[i][1].build(i);       kmp[i][1].build(i);       std::reverse(str[i] + 1, str[i] + 1 + len_str[i]);     }     acm[0].build(), acm[0].get_son(), acm[0].pre_dfn(0);     acm[1].build(), acm[1].get_son(), acm[1].pre_dfn(0);     bit[0].lim = acm[0].tim, bit[1].lim = acm[1].tim;     for (int t = 1; t <= q; ++t) {       IN(u, v, id);       int lca = Lca(u, v);       ans[t] = kmp_solve(u, v, lca, id);       int t1 = kth(u, min(dep[u], dep[lca] + len_str[id] - 1));       int t2 = kth(v, min(dep[v], dep[lca] + len_str[id] - 1));       if (t1 != u)         que_nod[u].push_back((Query){id, t, 1, 1}),             que_nod[t1].push_back((Query){id, t, 1, -1});       if (t2 != v)         que_nod[v].push_back((Query){id, t, 0, 1}),             que_nod[t2].push_back((Query){id, t, 0, -1});     }     get_ac_ans(1, 0, 0);     for (int i = 1; i <= q; ++i) printf( %d n , ans[i]);     return 0;   }   