File Encryption Tree Optimization

Problem: File Encryption Tree Optimization You are given a file-system tree. Each node is either a directory D or a file F. One encryption operation can be applied to either a file path or a directory path: Encrypting a file encrypts only that file; Encrypting a directory encrypts all descendant files under that directory. Given a set of target files that must be encrypted, output a path set with the minimum possible size such that: Every target file is encrypted; No non-target file is encrypted; The number of output paths is minimized. If all files under a directory are target files, you may output that directory path instead of all its descendant files. Input Format N TYPE path TYPE path ... TYPE path M target_file_path_1 target_file_path_2 ... target_file_path_M N is the number of file-system nodes; The next N lines each contain a node type and a path: D /a/b means a directory; F /a/b/c.txt means a file; M is the number of target files to encrypt; The next M lines contain target file paths. Output Format Output the minimum encryption path set in lexicographical order: K path_1 path_2 ... path_K where K is the minimum number of paths. Constraints 1 <= N <= 2 * 10^5; 0 <= M <= number of files; Every target path is guaranteed to be an existing file path from the input; Paths are Unix-style absolute paths, e.g. /a/b/c.txt; The root directory is / and may not be explicitly listed; The total length of all paths is at most 2 * 10^6. Example Input: 6 D /a D /a/b F /a/b/1.txt F /a/b/2.txt F /a/3.txt F /x.txt 2 /a/b/1.txt /a/b/2.txt Output: 1 /a/b Explanation: all files under /a/b are target files, so encrypting the whole directory /a/b is optimal. Example Input 6 D /a D /a/b F /a/b/1.txt F /a/b/2.txt F /a/3.txt F /x.txt 2 /a/b/1.txt /a/b/2.txt Output 1 /a/b