#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
const int MAXN = 100000 + 5;
 
int n;
vector<int> g[MAXN];
ll ans = 0;
 
inline ll f(ll x){ return x*(x+1)/2; }
 
void dfs(int u, set<int>& S, ll& avoid, const ll T){
    // insert u
    auto it = S.insert(u).first;
    auto itL = prev(it);
    auto itR = next(it);
    int L = *itL, R = *itR;
    ll big = R - L - 1;
    ll left = u - L - 1;
    ll right = R - u - 1;
 
    avoid = avoid - f(big) + f(left) + f(right);
 
    // contribute of node u
    ans += T - avoid;
    cout<<u<<" "<<T-avoid<<endl;
 
    for(int v : g[u]) dfs(v, S, avoid, T);
 
    // erase u (revert)
    avoid = avoid - f(left) - f(right) + f(big);
    S.erase(it);
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    if(!(cin >> n)) return 0;
    for(int i=2;i<=n;i++){
        int p; cin >> p;
        g[p].push_back(i);
    }
 
    const ll T = 1LL * n * (n + 1) / 2;
 
    set<int> S;               // giữ các nhãn tổ tiên đang active
    S.insert(0); S.insert(n+1); // lính gác để tính khoảng
    ll avoid = f(n);          // ban đầu một khoảng trống dài n
 
    dfs(1, S, avoid, T);
 
    cout << ans << "\n";
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp1c2luZyBsbCA9IGxvbmcgbG9uZzsKY29uc3QgaW50IE1BWE4gPSAxMDAwMDAgKyA1OwoKaW50IG47CnZlY3RvcjxpbnQ+IGdbTUFYTl07CmxsIGFucyA9IDA7CgppbmxpbmUgbGwgZihsbCB4KXsgcmV0dXJuIHgqKHgrMSkvMjsgfQoKdm9pZCBkZnMoaW50IHUsIHNldDxpbnQ+JiBTLCBsbCYgYXZvaWQsIGNvbnN0IGxsIFQpewogICAgLy8gaW5zZXJ0IHUKICAgIGF1dG8gaXQgPSBTLmluc2VydCh1KS5maXJzdDsKICAgIGF1dG8gaXRMID0gcHJldihpdCk7CiAgICBhdXRvIGl0UiA9IG5leHQoaXQpOwogICAgaW50IEwgPSAqaXRMLCBSID0gKml0UjsKICAgIGxsIGJpZyA9IFIgLSBMIC0gMTsKICAgIGxsIGxlZnQgPSB1IC0gTCAtIDE7CiAgICBsbCByaWdodCA9IFIgLSB1IC0gMTsKCiAgICBhdm9pZCA9IGF2b2lkIC0gZihiaWcpICsgZihsZWZ0KSArIGYocmlnaHQpOwoKICAgIC8vIGNvbnRyaWJ1dGUgb2Ygbm9kZSB1CiAgICBhbnMgKz0gVCAtIGF2b2lkOwogICAgY291dDw8dTw8IiAiPDxULWF2b2lkPDxlbmRsOwoKICAgIGZvcihpbnQgdiA6IGdbdV0pIGRmcyh2LCBTLCBhdm9pZCwgVCk7CgogICAgLy8gZXJhc2UgdSAocmV2ZXJ0KQogICAgYXZvaWQgPSBhdm9pZCAtIGYobGVmdCkgLSBmKHJpZ2h0KSArIGYoYmlnKTsKICAgIFMuZXJhc2UoaXQpOwp9CgppbnQgbWFpbigpewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luLnRpZShudWxscHRyKTsKCiAgICBpZighKGNpbiA+PiBuKSkgcmV0dXJuIDA7CiAgICBmb3IoaW50IGk9MjtpPD1uO2krKyl7CiAgICAgICAgaW50IHA7IGNpbiA+PiBwOwogICAgICAgIGdbcF0ucHVzaF9iYWNrKGkpOwogICAgfQoKICAgIGNvbnN0IGxsIFQgPSAxTEwgKiBuICogKG4gKyAxKSAvIDI7CgogICAgc2V0PGludD4gUzsgICAgICAgICAgICAgICAvLyBnaeG7ryBjw6FjIG5ow6NuIHThu5UgdGnDqm4gxJFhbmcgYWN0aXZlCiAgICBTLmluc2VydCgwKTsgUy5pbnNlcnQobisxKTsgLy8gbMOtbmggZ8OhYyDEkeG7gyB0w61uaCBraG/huqNuZwogICAgbGwgYXZvaWQgPSBmKG4pOyAgICAgICAgICAvLyBiYW4gxJHhuqd1IG3hu5l0IGtob+G6o25nIHRy4buRbmcgZMOgaSBuCgogICAgZGZzKDEsIFMsIGF2b2lkLCBUKTsKCiAgICBjb3V0IDw8IGFucyA8PCAiXG4iOwogICAgcmV0dXJuIDA7Cn0K

Ngo1IDUgMSAxIDQK

6
5 5 1 1 4