[CERC2017] Hidden Hierarchy

## 题目描述 假设你正在开发一个简单的以输入文字为基础的文件夹浏览器。你的工作之一就是要构建一个导航目录来显示这些文件夹的上下关系。通常而言，这些文件夹很可能是互相嵌套的——比如，某个文件夹下还有一个文件夹，当然也可能会包含某些文件。因此，这些文件夹会形成一种树状结构。在这个目录中，最顶端的那个文件夹称之为根目录。如果文件夹d中直接含有文件夹e，那么我们称之为文件夹d是文件夹e的父文件夹，而文件夹e是文件夹d的子文件夹。每个文件都有一个用字节数来表示的大小。一个文件夹的大小是被直接或不直接包含于其中的所有文件的大小之和。 所有的文件和文件夹（除根目录外）都有一个名字——一个只由小写字符和点（“."）组成并且只由小写字母开头的字符串。包含于同一个父目录下的文件或文件夹的名字必定各不相同。而且，路径与文件是一一对应的。生成路径的规则如下： - 根目录路径是“/” - 文件夹d的路径是从根目录开始，沿着文件夹的父子关系，顺次往下，在每个文件夹名字前添加一个“/”，相互连接，并在路径的最末尾添加一个“/”。 - 文件f的路径是由它的父文件夹的路径加上文件名得到的。 通过打印根目录，我们能够显示文件夹的上下父子关系。打印文件夹d时，我们输出一个“md pd sd”形式的字符串。其中，pd是文件夹d的路径，sd是文件夹d的大小，md是文件夹d的扩展标记。如果文件夹d包含其他文件夹，我们可以选择是否展开它。如果我们要展开文件夹d，我们就要以字典序打印它里面包含的所有文件和文件夹。如果我们不打开文件夹d，那么我们就可以忽略其中的内容。 如果d是一个空文件夹（即没有包含任何文件或文件夹），那么md就仅仅是一个空字符。当我们要展开这个文件夹的时候，md是一个“-”，而如果我们不展开这个文件夹的是md是一个“+”。 现在，输入一列文件和一个限制性整数t。请你打印（按照前述展开打印方法）所有的大小不小于t的文件夹。并且，打印的文件夹总数一定是最小的。保证不存在空文件夹即整个文件夹上下关系都可从输入的文件路径中推断得出。注意，大小不小于t的文件夹必须要被打印，但不一定要展开。根目录不论多大都要被打印。 ## 输入输出格式 ### 输入格式 第一行输入包含一个整数n（1<=n<=1000）表示文件的总数。之后的n行中，每行包含一个字符串f和一个整数s（1<=s<=10^6）。其中，f表示文件路径和单个文件的大小。每个路径最多含有100个字符并保证是一个合法路径。所有的路径保证各不相同。 之后的一行包含限制性整数t（1<=t<=10^9）。 ### 输出格式 按照前述方法输出最少的展开文件的方法。

You are working on the user interface for a simple text-based file explorer. One of your tasks is to build a navigation pane displaying the directory hierarchy. As usual, the filesystem consists of directories which may contain files and other directories, which may, in turn, again contain files and other directories etc. Hence, the directories form a hierarchical tree structure. The top-most directoryin the hierarchy is called the root directory. If directory $d$ directly contains directory $e$ we will say that $d$ is the parent directory of $e$ while $e$ is a subdirectory od $d$. Each file has a size expressed in bytes. The directory size is simply the total size of all files directly or indirectly contained inside that directory. All files and all directories except the root directory have a name — a string that always starts with a letter and consists of only lowercase letters and “``.``” (dot) characters. All items (files and directories) directly inside the same parent directory must have unique names. Each item (file and directory) can be uniquely described by its path — a string built according to the following rules: - Path of the root directory is simply “``/``” (forward slash). - For a directory $d$, its path is obtained by concatenating the directory names top to bottom along the hierarchy from the root directory to $d$, preceding each name with the “``/``” character and placing another “``/``” character at the end of the path. - For a file $f$ , its path is the concatenation of the parent directory path and the name of file $f$ . We display the directory hierarchy by printing the root directory. We print a directory $d$ by outputting a line of the form “$m_d \ p_d \ s_d$” where $p_d$ and $s_d$ are the path and size of directory $d$ respectively, while $m_d$ is its expansion marker explained shortly. If $d$ contains other directories we must choose either to collapse it or to expand it. If we choose to expand $d$ we print (using the same rules) all of its subdirectories in lexicographical order by name. If we choose to collapse directory $d$, we simply ignore its contents. The expansion marker $m_d$ is a single blank character when $d$ does not have any subdirectories, “``+``” (plus) character when we choose to collapse $d$ or a “``-``” (minus) character when we choose expand $d$. Given a list of files in the filesystem and a threshold integer $t$, display the directory hierarchy ensuring that each directory of size at least $t$ is printed. Additionally, the total number of directories printed should be minimal. Assume there are no empty directories in the filesystem — the entire hierarchy can be deduced from the provided file paths. Note that the root directory has to be printed regardless of its size. Also note that a directory of size at least $t$ only has to be printed, but not necessarily expanded.

The first line contains an integer $n(1 \le n \le 1 000)$ — the number of files. Each of the following $n$ lines contains a string $f$ and an integer $s(1 \le s \le 10^6)$ — the path and the size of a single file. Each path is at most $100$ characters long and is a valid file path according to the rules above. All paths will be different. The following line contains an integer $t(1 \le t \le 10^9)$ — the threshold directory size.

Output the minimal display of the filesystem hierarchy for the given threshold as described above.

9
/sys/kernel/notes 100
/cerc/problems/a/testdata/in 1000000
/cerc/problems/a/testdata/out 8
/cerc/problems/a/luka.cc 500
/cerc/problems/a/zuza.cc 5000
/cerc/problems/b/testdata/in 15
/cerc/problems/b/testdata/out 4
/cerc/problems/b/kale.cc 100
/cerc/documents/rules.pdf 4000
10000

- / 1009727
- /cerc/ 1009627
/cerc/documents/ 4000
- /cerc/problems/ 1005627
- /cerc/problems/a/ 1005508
/cerc/problems/a/testdata/ 1000008
+ /cerc/problems/b/ 119
+ /sys/ 100

8
/b/test/in.a 100
/b/test/in.b 1
/c/test/in.a 100
/c/test/in.b 1
/c/test/pic/in.a.svg 10
/c/test/pic/in.b.svg 10
/a/test/in.a 99
/a/test/in.b 1
101

- / 322
+ /a/ 100
- /b/ 101
/b/test/ 101
- /c/ 121
+ /c/test/ 121

2
/a/a/a 100
/b.txt 99
200

+ / 199