Problem Description

Given a tree with nodes numbered from $1$ to $n$, where node $1$ is the root. Each node has a color $C_i$.

If, in a tree, the number of nodes for every color that appears is the same, then we call it a color-balanced tree.

Find how many subtrees of this tree are color-balanced trees.

Input Format

The first line contains an integer $n$, representing the number of nodes in the tree.

The next $n$ lines each contain two integers $C_i, F_i$, separated by a space, representing the color of node $i$ and the index of its parent node.

In particular, the input guarantees that $F_1$ is $0$, meaning node $1$ has no parent. The input is guaranteed to form a tree.

Output Format

Output one line containing an integer, representing the answer.

6
2 0
2 1
1 2
3 3
3 4
1 4

4

Hint

Sample Explanation

The subtrees rooted at nodes $1, 3, 5, 6$ are color-balanced trees.

Constraints

For $30\%$ of the testdata, $n \leq 200$, $C_i \leq 200$.

For $60\%$ of the testdata, $n \leq 5000$, $C_i \leq 5000$.

For all testdata, $1 \leq n \leq 2\times 10 ^ 5$, $1 \leq C_i \leq 2\times 10 ^ 5$, $0 \leq F_i<i$.

Translated by ChatGPT 5