样例通过了，但是结果一个都不对... 请问哪里错了呢?

#include <iostream>
#include <queue>
#include <string>
#include <map>
#include <cstring>
#include <deque>
#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>

using namespace std;

const int kSiz = 1e6 + 8;
const int kLog = 20;

struct Node {
    int nxt[26];
    int cnt;
};

int N, head = 1;

int dep[kSiz];
int fa[kSiz][kLog];
int root[kSiz];
Node tree[kSiz * 12];

int lca(int x, int y) {
    if (dep[x] < dep[y]) {
        swap(x, y);
    }
    for (int i = kLog - 1;i >= 0;i--) {
        if (dep[fa[x][i]] >= dep[y]) {
            x = fa[x][i];
        }
    }
    if (x == y) return x;
    for (int i = kLog - 1;i >= 0;i--) {
        if (dep[x] != dep[y]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}

void modify(int old, int now, const string& s) {
    tree[now] = tree[old];
    if (!s.empty()) {
        tree[now].cnt++;
    }

    for (int i = 0; s[i];++i) {
        int idx = s[i] - 'a';

        tree[now].nxt[idx] = head;
        int cld = tree[old].nxt[idx];
        tree[head] = tree[cld];
        tree[head].cnt++;

        old = cld;
        now = head;

        head++;
    }
}

vector < vector<pair<int, string> > > edge;
void dfs(int x, int p, const string& s) {
    dep[x] = dep[p] + 1;
    fa[x][0] = p;
    for (int i = 1;i < kLog;++i) {
        int t = fa[x][i - 1];
        fa[x][i] = fa[t][i - 1];
    }
    root[x] = head++;
    modify(root[p], root[x], s);

    for (auto& it : edge[x]) {
        if (it.first != p) {
            dfs(it.first, x, it.second);
        }
    }
}

int travel(int r, const string& s) {
    for (int i = 0; s[i];++i) {
        int idx = s[i] - 'a';
        r = tree[r].nxt[idx];
    }
    return tree[r].cnt;
}

void query(int x, int y, string& s) {
    int p = lca(x, y);

    int a = travel(root[x], s);
    int b = travel(root[y], s);
    int c = travel(root[p], s);
    cout << a + b - c * 2 << endl;
    // cout << a << " " << b << " " << c << endl;
}

bool vis[kSiz];
void ndfs(int p) {
    if (vis[p]) {
        return;
    }
    vis[p] = true;

    printf("\t%d [label = \"%d, %d\"]\n", p, p, tree[p].cnt);
    for (int i = 0; i < 26; ++i) {
        char s = ('a' + i);
        int n = tree[p].nxt[i];
        if (n) {
            printf("\t%d -> %d[label = \"%c\"]\n", p, n, s);
            ndfs(n);
        }
    }
}

void work() {
    cin >> N;
    edge.resize(N + 1);

    int a, b;
    string s;
    for (int i = 1;i < N;++i) {
        cin >> a >> b >> s;
        edge[a].push_back({ b, s });
        edge[b].push_back({ a, s });
    }

    s = "";
    dfs(1, 0, s);

    int Q;
    cin >> Q;
    for (int i = 0; i < Q;++i) {
        cin >> a >> b >> s;
        query(a, b, s);
    }

    // printf("digraph G {\n");
    // for (int i = 1; i <= N; ++i) {
    //     ndfs(root[i]);
    // }
    // printf("}\n");
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    work();

    return 0;
}