P15295 [ROI 2012 Day 1] virus Virus and Antivirus Software.

Translation source: [loj #5456. "ROI 2012 Day 1" Virus and Antivirus Software](https://loj.ac/p/5456).

An antivirus IT company has an official management hierarchy. In this structure, there is a boss who is the only employee without a supervisor. Every other employee has exactly one direct supervisor. Each supervisor can have multiple subordinates, and can pass orders to any subordinate either directly or through a chain of subordinates. Orders can only be passed along chains from supervisors to subordinates. In this hierarchy, if employee $A$ can pass orders to employee $B$ either directly or through a chain of subordinates, then $A$ is said to have a higher status than $B$. The boss has a higher status than any employee. However, it is discovered that all employees also form a similar secret hierarchy used to develop computer viruses. In this secret structure, the boss and the supervisor relationships may be different. We call a pair of employees $A$ and $B$ a **stable pair** if $A$ has a higher status than $B$ in both the official hierarchy and the secret hierarchy. You need to write a program to compute the number of stable pairs in the company.

The first line of the input file contains an integer $N$ $(1 \leq N \leq 100000)$, representing the number of employees in the company. The second line contains $N$ integers $a_i$. If employee $i$ is the boss in the official hierarchy, then $a_i = 0$; otherwise, $a_i$ is the index of this employee’s direct supervisor. The third line contains $N$ integers $b_i$. If employee $i$ is the boss in the secret hierarchy, then $b_i = 0$; otherwise, $b_i$ is the index of this employee’s direct supervisor. Employees are numbered starting from $1$, in the order mentioned in the input file.

The output file should contain one integer, the number of stable pairs.

The detailed additional constraints and scores for each subtask are shown in the table below: | Subtask | Score | Additional Constraints | | :-----: | :---: | :--------------------: | | $1$ | $25$ | Number of employees $N \leq 100$ | | $2$ | $25$ | Number of employees $N \leq 2000$ | | $3$ | $50$ | Number of employees $N \leq 100000$ | Translated by ChatGPT 5