408272: GYM103075 E Рудольф и файловая система

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Рудольф и файловая системаограничение по времени на тест3 секундыограничение по памяти на тест64 мегабайтавводстандартный вводвыводстандартный вывод

Рудольф только что переустановил операционную систему на своём ноутбуке и сейчас занят формированием привычной ему иерархии директорий и документов.

Элементами файловой системы являются файлы и папки. Каждый файл или папка размещаются внутри некоторой другой папки; единственным исключением из этого правила является корневая папка — для неё родительской папки не существует.

Каждый файл имеет определённый размер в байтах. Размером папки считается сумма размеров всех содержащихся в ней файлов, а также всех содержащихся в ней папок. Размер пустой папки равен нулю.

Оказывается, Рудольфа раздражают ситуации, когда в какой-то папке становится слишком много или слишком мало файлов. Поэтому Рудольф то и дело перемещает файлы из одних папок в другие, а также проверяет размер папок.

Помогите Рудольфу автоматизировать его работу с файловой системой.

Входные данные

Первая строка содержит слово $$$R$$$ — имя корневой папки.

Вторая строка содержит целое число $$$N$$$ ($$$1 \le N \le 10^5$$$) — количество элементов (файлов и папок) в файловой системе, не считая корневой папки.

Следующие $$$N$$$ строк описывают элементы файловой системы. Каждая из них содержит целое число $$$T_i$$$ ($$$T_i \in \{0, 1\}$$$), слово $$$S_i$$$ и слово $$$P_i$$$ — соответственно тип элемента ($$$0$$$ — папка, $$$1$$$ — файл), название элемента и название папки, в которой он размещён. Если $$$T_i = 1$$$, то далее следует целое число $$$V_i$$$ ($$$1 \le V_i \le 10^9$$$) — размер файла в байтах.

Следующая строка содержит целое число ($$$1 \le Q \le 10^5$$$) — количество действий Рудольфа.

Следующие $$$Q$$$ строк описывают действия Рудольфа. Каждая из них содержит целое число $$$T_j$$$ ($$$T_j \in \{0, 1\}$$$) — вид действия ($$$0$$$ — вычисление размера папки, $$$1$$$ — перемещение файла). Если $$$T_j = 0$$$, то далее следует слово $$$S_j$$$ — имя папки, у которой вычисляется размер. Если $$$T_j = 1$$$, то далее следуют слова $$$S_j$$$ и $$$P_j$$$ — соответственно имя перемещаемого файла и имя папки, в которую он перемещается.

Имена всех элементов файловой системы уникальны, состоят из строчных латинских букв и имеют длину от 1 до 20 символов.

Выходные данные

Для каждого действия вида $$$0$$$ выведите одно целое число: суммарный размер в байтах всех файлов, расположенных в интересующей папке и её подпапках.

ПримерыВходные данные
root
7
0 foldone root
0 foldtwo root
0 foldthree foldone
0 foldfour foldone
1 fileone foldfour 10
1 filetwo foldfour 5
1 filethree foldtwo 7
5
0 foldone
1 fileone foldthree
0 foldone
0 foldthree
0 foldtwo
Выходные данные
15
15
10
7
Входные данные
home
1
0 srv home
1
0 home
Выходные данные
0

加入题单

算法标签: