Compute effective permissions on DAG and prune tree

Problem A — Effective allow/disallow letters on a DAG

You are given a directed acyclic graph (DAG) with n nodes labeled 0..n-1.

Each node u contains two (possibly empty) sets of lowercase letters:

• allow[u] — letters explicitly allowed at u
• deny[u] — letters explicitly disallowed at u

Transitivity rule (inheritance along edges): if there is a directed edge u -> v, then v inherits all rules from u (and from all of u’s ancestors).

Define for each node v:

• A(v) : union of allow[x] over all ancestors x of v (including v itself)
• D(v) : union of deny[x] over all ancestors x of v (including v itself)
• effective(v) = A(v) \ D(v) (denies override allows)

Task: For every node v, output its effective(v) set.

Notes/assumptions:

• The graph is guaranteed to be a DAG.
• Letters are from 'a'..'z' .
• If a letter appears in both allow and deny along the ancestry, it is not effective.

Problem B — Tree pruning / depth constraints (3 related tasks)

You are given a rooted tree with n nodes labeled 0..n-1, rooted at node 0. Depth of the root is 0.

Deleting a node removes that node and its entire subtree.

Task B1

You are given a list/set of nodes to delete. After performing all deletions, the remaining nodes form a forest.

Output: the maximum depth (in the original tree’s depth numbering) among all remaining nodes. If nothing remains, output -1.

Task B2

Given an integer N, delete the minimum number of nodes (each deletion removes a whole subtree) so that the maximum remaining depth is at most N.

Output: the minimum number of deleted nodes.

Task B3 (bonus)

Same as Task B2, but if multiple deletion plans achieve the minimum number of deletions, choose one that maximizes the sum of depths of the deleted nodes.

Output:

• the minimum number of deleted nodes, and
• the maximum possible sum of depths of deleted nodes among minimum-deletion solutions.

Constraints (you may assume for all tasks):

• 1 <= n <= 2e5
• Tree given as parent array or edge list.
• DAG given as edge list.
• Aim for near-linear or O((n+m) * 26) / O((n+m) * word_bitset) type solutions.