#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
class Solution
{
public:
    vector<vector<int>> children; //各个节点的子节点坐标
    int countHighestScoreNodes(vector<int> &parents)
    {
        int n = parents.size();
        vector<int> tree(2 * n + 2, -1); //线性表构成的树,-1表示空
        vector<int> left(2 * n + 2, 0);  //左右子结点数
        vector<int> right(2 * n + 2, 0);
        map<long long, int> m;
        long long maxAns = 0;
        children.resize(n);
        for (int i = 1; i < n; i++)
        {
            children[parents[i]].push_back(i); //通过父节点记录子结点
        }
        tree[1] = 0;
        for (int i = 1; i <= n; i++)
        {
            if (tree[i] != -1)
            {
                for (int j = 0; j < children[tree[i]].size(); j++)
                {
                    if (j == 0)
                        tree[2 * i] = children[tree[i]][j];
                    else if (j == 1)
                        tree[2 * i + 1] = children[tree[i]][j];
                }
            }
        }

        for (int i = 1; i <= 2 * n + 1; i++)
            printf("%d ", tree[i]);

        for (int i = 2 * n + 1; i >= 1; i--)
        {
            if (tree[i] != -1)
            {
                int parent = i / 2;
                if (i % 2 == 0)
                    left[parent] += left[i] + right[i] + 1;
                else
                    right[parent] += left[i] + right[i] + 1;
            }
        }
        for (int i = 1; i <= 2 * n + 1; i++)
        {
            if (tree[i] < 0)
                continue;
            long long temp = 1;
            if (left[i] != 0)
                temp *= left[i];
            if (right[i] != 0)
                temp *= right[i];
            int root = n - left[i] - right[i] - 1;
            if (root > 0)
                temp *= root;
            if (temp >= maxAns)
            {
                maxAns = temp;
                m[maxAns]++;
            }
        }
        return m[maxAns];
    }
};
int main()
{
    Solution *s = new Solution();
    vector<int> parents{-1, 9, 1, 0, 3, 4, 5, 11, 5, 10, 0, 3, 13, 6, 8, 1};
    int ans = s->countHighestScoreNodes(parents);
    // cout << ans << endl;
    return 0;
}