Recall the definition of a trie:
A trie of size
�
n is a rooted tree with
�
n vertices and
(
�
−
1
)
(n−1) edges, where each edge is marked with a character;
Each vertex in a trie represents a string. Let
�
(
�
)
s(x) be the string vertex
�
x represents;
The root of the trie represents an empty string. Let vertex
�
u be the parent of vertex
�
v, and let
�
c be the character marked on the edge connecting vertex
�
u and
�
v, we have
�
(
�
)
s(v) =
�
(
�
)
+
�
s(u)+c. Here
+
+ indicat