410784: GYM104103 E Comparing Theories

Testing hypotheses and theories is an integral part of the scientific process. One of the most essential questions in evolutionary biology is studying the history of how the species developed; when and how the species evolution diverged into new species. In this problem, you will evaluate the difference between two evolutionary hypotheses, represented as trees.

The evolutionary history of $$$n$$$ modern species can be represented as a binary tree with $$$n$$$ leaves corresponding to those $$$n$$$ species. Each internal vertex corresponds to an extinct species that, at some point in time, had diverged into two other species. The root of this tree is a hypothetical "primordial" species, a predecessor to all modern species. The leaves are numbered from $$$1$$$ to $$$n$$$; the other vertices have numbers from $$$n + 1$$$ to $$$2n - 1$$$. The vertex $$$2n - 1$$$ is the root of the tree.

To compare two evolutionary theories, scientists use different metrics, one of them is called "triplet distance". Consider three different modern species (leaves in the tree). Go up the evolutionary tree from those species and find two species where these three modern species diverged. For three modern species $$$A$$$, $$$B$$$, and $$$C$$$, there are, essentially, three different evolutionary structures (shown in the picture below): the common ancestor split into one species that then evolved into $$$A$$$ and $$$B$$$, and another one, that eventually evolved into $$$C$$$. Similarly, there are two more structures with different partitions. We'll say that, for a given triple $$$(A, B, C)$$$, its history is different in two theories if these basic structures differ. Shown below are the three different historic structures for the three modern species. Every edge in the picture might be a chain of multiple intermediate species.

Find the number of triples of modern species with different historic structures in the two given evolutionary trees.

The first line contains one integer $$$n$$$ ($$$3 \le n \le 50\,000$$$) — the number of modern species (also the number of leaves in the tree). Then, two lines describing the trees follow.

Each tree is represented as an array of parents of length $$$2n - 2$$$: for every vertex $$$i$$$ from $$$1$$$ to $$$2n - 2$$$, you are given the number of its parent in the tree $$$\t{parent[}i\t{]} > i$$$. Vertex number $$$2n - 1$$$ is the root of the tree. It's guaranteed that the vertices $$$1$$$ to $$$n$$$ are leaves, and they don't appear as values in the parent array. It is also guaranteed that the tree is a binary tree: each internal vertex has a number from $$$n + 1$$$ to $$$2n - 1$$$ and has exactly two children (that is, all these values appear exactly twice in the parent array).

Print a single integer — the number of triples of species with different evolutionary histories.

5
6 9 7 6 7 8 8 9
6 9 7 7 6 8 8 9

4

5
8 7 7 6 6 8 9 9
7 8 6 9 6 7 8 9

8

These are the two trees from the first example:

Triples with different evolutionary histories: $$$(1, 3, 4), (1, 3, 5), (1, 4, 5), (3, 4, 5)$$$.

The second example:

There are 8 different triples: $$$(1, 2, 3), (1, 2, 4), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 5), (2, 4, 5), (3, 4, 5)$$$.