Cách 1

Nhận xét

Cả cây chỉ có thể tạo ra 1 "trie" mà không cập nhật.

Solution:

Từ cây trong đề ta sẽ dựng một trie, với mỗi nút trie lưu thêm các đỉnh thuộc cây ban đầu.

Khi truy vấn ~u~, ~s~ thì ta sẽ tìm lại vị trí của đỉnh ~u~ trên trie và dần đi xuống theo các phần tử của ~s~.

Khi đi hết chuỗi ~s~ ta đếm số lượng đỉnh thuộc cây con gốc ~u~.

Để lưu vào các đỉnh vào trie, ta sẽ dùng kĩ thuật "Euler tour" để lưu theo chỉ số của đỉnh trên euler tour, sau đó sắp xếp và chặt nhị phân để tính số lượng.

Cách 2

Ta sẽ xử lí truy vấn offline.

Chọn đỉnh ~1~ là gốc của cây.

Với mỗi đỉnh u, ta sẽ lưu một Trie gồm các xâu ~t(u, v)~ với v nằm trong cây con của u.

Ta có thể nhận xét rằng, số node của cây Trie của đỉnh u sẽ bé hơn hoặc bằng độ lớn của cây con gốc u.

Từ đó, ta có thể dùng kĩ thuật Small To Large để gộp các Trie lại với nhau. Việc gộp này ta sẽ dùng DFS trên Trie có số node bé hơn để add dần vào Trie còn lại.

#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
const int maxN = 2e5 + 5;
const int maxQ = 2e5 + 5;



int n, q;
char a[maxN];
std::vector <int> adj[maxN];

struct query {
    int idx;
    std::string s;
    query(int _idx, const std::string _s) : idx(_idx), s(_s) {}
};

std::vector <query> Q[maxN]; 
std::vector <int> newTree[maxN];
struct node {
    int nxt[26] = {};
    node (){};

    int& operator[](char ch) {
        return nxt[ch - 'a'];
    }
};

std::vector <node> trie(1);

int in[maxN], out[maxN], cnt;


std::vector <int> save[26 * maxN];
int id[maxN];


void dfs(int p, int u, int pos) {
    in[u] = ++cnt; 
    if (trie[pos][a[u]] == 0) {
        trie[pos][a[u]] = trie.size();
        trie.push_back(node());
    }

    int nxtPos = trie[pos][a[u]];
    id[u] = pos;
    save[nxtPos].push_back(in[u]);

    for (int v: adj[u]) if (v != p)
        dfs(u, v, nxtPos);

    out[u] = cnt;
}

int main() {

    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cin >> n >> q;
    for (int i = 1; i <= n; i ++)
        std::cin >> a[i];

    for (int i = 1, u, v; i < n; i ++) {
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(0, 1, 0);

    for (int i = 1; i < trie.size(); i ++)
        std::sort(save[i].begin(), save[i].end());

    for (int i = 1; i <= q; i ++) {
        int u;
        std::string s;
        std::cin >> u >> s;

        int pos = id[u];
        for (char ch: s) {
            pos = (trie[pos][ch] ? trie[pos][ch] : -1);
            if (pos == -1) break;
        }

        if (pos == -1) 
            std::cout << 0 << '\n';
        else {
            int l = in[u], r = out[u];
            int L = std::lower_bound(save[pos].begin(), save[pos].end(), l) - save[pos].begin();
            int R = std::upper_bound(save[pos].begin(), save[pos].end(), r) - save[pos].begin();
            std::cout << std::max(0, R - L) << '\n';
        } 
    }

    return 0;
}