Background

Translation source: loj #5456. "ROI 2012 Day 1" Virus and Antivirus Software.

Problem Description

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.

Input Format

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.

Output Format

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

3
0 3 1
0 1 1

2

5
2 0 1 3 4
3 1 0 2 4

7

Hint

The detailed additional constraints and scores for each subtask are shown in the table below:

Translated by ChatGPT 5