Minimum-cost encryption of a directory tree

A storage service keeps a filesystem as a tree:

class FileNode:
    name: str
    is_encrypted: bool

class DirectoryNode:
    name: str
    directories: list["DirectoryNode"]   # child directories
    files: list[FileNode]                # files directly inside

Compliance requires every file in the tree to end up encrypted. You can issue two kinds of calls:

• encrypt(file_path) costs file_cost and encrypts one file.
• encrypt(dir_path) costs dir_cost and encrypts every file anywhere under that directory.

Part 1

Return the number of encrypted and unencrypted files in the tree, as (encrypted, unencrypted).

Part 2

Return the minimum total cost and one list of paths (/root/sub/file) that achieves it. Re-encrypting an already-encrypted file is harmless. Do not issue calls for subtrees that need no work.

Part 3

Encrypting an already-encrypted file now corrupts it, so a directory call is only allowed when no file in its subtree is encrypted yet. Return the new minimum cost and plan.

Constraints

• Up to 10^5 nodes; the tree can be thousands of levels deep.
• 1 <= file_cost, dir_cost <= 10^6.
• Names inside one directory are unique.

Example

/media
  intro.txt          plain
  photos/  p1 p2 p3 p4   all plain
  backup/  b1 (encrypted), b2 plain

• Part 1: (1, 6).
• Part 2 with file_cost = 1, dir_cost = 3: photos costs 3 as one call (instead of 4). The children of /media then cost 1 + 3 + 1 = 5, so one call on /media (cost 3) wins. Answer: cost 3, ["/media"].
• Part 3 with the same costs: /media and /media/backup are not allowed. Answer: cost 5, ["/media/intro.txt", "/media/photos", "/media/backup/b2"].

Reconstructed from the reported question; details may differ from what interviewers ask.