# Tree String

## Đề Bài

Cho cây gồm $n$ đỉnh có gốc tại đỉnh $1$, đỉnh thứ $i$ chứa kí tự $c_i$ (nằm trong bảng chữ cái alphabet viết thường).

Gọi $t(u,v)$ là xâu được tạo thành bằng các kí tự trên các đỉnh trong đường đi đơn từ đỉnh $u$ tới đỉnh $v$.

Ta có $q$ truy vấn, truy vấn thứ $i$ có dạng như sau:
- Cho đỉnh $u_i$ và xâu $s_i$, hãy đếm xem có bao nhiêu $t(u_i,v) = s_i$, sao cho $v$ thuộc cây con của đỉnh $u$.

#### Giới hạn

- $1 \le n,q \le 2 \times 10^5$.
- Tổng các $|s_i|$ trong các truy vấn không quá $5 \times 10^5$.

## Editorial

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

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.