Давайте поддерживать бор имен файлов. Тогда, чтобы посчитать ответ для файла, нужно спуститься в боре по его имени и посчитать количество вершин на пути, в которых нужно нажать на кнопку. В корне всегда нужно нажать на кнопку. В вершинах, у которых хотя бы два ребенка или в которых заканчивается какое-либо имя файла, нужно нажать на кнопку, соответствующую букве. В вершинах, в которых не нужно нажимать на букву, но в родителях которых нужно нажимать на букву, нужно нажимать на tab. Таким образом, мы получили решение за $$$O(q \cdot L)$$$, где $$$L$$$ — максимальная возможная длина строки.

Теперь заметим, что при добавлении и удалении имени, значение «нужно ли нажимать на кнопку в вершине» изменяется у не более чем $$$l \cdot \Sigma$$$ вершин (это вершины, принадлежащие пути, соответствующему имени, а также их дети). Суммарная длина добавляемых и удаляемых имен не превышает $$$2 \cdot 10 ^ 6$$$, потому что каждое добавляемое имя удаляется не более одного раза, а суммарная длина добавляемых имен не превышает $$$10 ^ 6$$$. В свою очередь, для ответа на третий запрос, нужно посчитать сумму на пути от корня до вершины. Это стандартная задача, которая решается за $$$O(\log n)$$$ на запрос с помощью дерева отрезков. Итоговая асимптотика решения получилась $$$O(q \cdot \log n + n \cdot \Sigma \cdot \log n)$$$, где $$$n$$$ — суммарная длина имен, а $$$\Sigma$$$ — размер алфавита, т.е. $$$26$$$.