#C10355. Packet Propagation in a Firewall-Protected Binary Tree

    ID: 39551 Type: Default 1000ms 256MiB

Packet Propagation in a Firewall-Protected Binary Tree

Packet Propagation in a Firewall-Protected Binary Tree

In this problem, you are given a binary tree network with n nodes and the relationships of parent-child nodes, where the root node (node with parent -1) initially holds a packet. The tree is protected by firewalls located at some nodes. A firewall, when activated, blocks its entire subtree from receiving the packet. Your task is to determine the number of leaf nodes that will receive the packet from the root, provided that if any node along the path from a leaf to the root (including the leaf itself) is blocked by a firewall, the packet will not reach that leaf.

Note: All formulas must be written in LaTeX format. For example, the binary tree is defined by ( n ) nodes, the parent array ( P ), where ( P[i] = -1 ) indicates the root, and the list of firewalls is given by ( F ).

inputFormat

The input is read from standard input (stdin) and consists of the following:

  1. A single integer ( n ) representing the number of nodes in the tree.
  2. A line containing ( n ) space-separated integers representing the parent indices of the nodes. For the root, the value is -1. The nodes are numbered from 1 to ( n ) (the first element corresponds to node 1, the second to node 2, and so on).
  3. An integer ( k ) representing the number of firewalls.
  4. A line containing ( k ) space-separated integers, each indicating a node where a firewall is installed. If ( k = 0 ), this line may be empty.

outputFormat

Print a single integer to standard output (stdout) denoting the number of leaf nodes that will receive the packet.## sample

7
-1 1 1 2 2 3 3
2
2 5
2