<h2>题目描述</h2>

给 $n$ 个节点的树。定义 $g(a,b)$ 表示 $a$ 的子树中除 $b$ 之外深度不超过 $b$ 的节点个数，定义 $f(v) = \sum_{x \in anc(v)} g(x,v)$ (其中 $anc(v)$ 是 $v$ 的祖先组成的集合)。
现在要对于每一个点，求出 $f(v)$
$n \leq 10^5$

<h2>题解</h2>

如果这题 $n \leq 10^5$ 那还是很 eazy 的。。可惜。。
首先我们对 $f(v)$ 求的东西做一个转化：我们考虑每个点 $i$ 只有在 $dep_i \leq dep_v$ 的时候会被贡献到，并且会被贡献 $dep_{lca(v,i)}$ 次。
也就是说 $f(v) = \sum_{dep_x \leq dep_v} dep_{lca(v,x)}$
我们分层考虑计算答案，发现每个节点会在它到根的路径上有贡献，查询节点的答案时只需要查询到根的和就好了（这样会在 lca 处被算到应该的次数），直接使用树链剖分。
但是这是两个 log，显然过不去。。
考虑我们每层的节点都按照 dfn 排序，现在计算这个点 $v$ 的答案，考虑如果转移到 dfn 更大的一个点 $v'$ 的时候，其他的点的 $dep$ 是单调不增的（最近的一段会变成现在的 lca，再往后就是之前的 lca）。我们可以用一个单调栈轻松维护。

/*
 * Author: RainAir
 * Time: 2019-10-09 20:20:00
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5e5 + 5;
const int MAXM = 19;

struct Edge{
    int to,nxt;
}e[MAXN<<1];
int n;
int head[MAXN],fMAXN,dep[MAXN],dfn[MAXN],cnt;
std::vector<int> G[MAXN];

inline void add(int u,int v){
    e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,head[v]};head[v] = cnt;
}

inline void dfs(int v,int fa=0){
    static int ts = 0;
    dfn[v] = ++ts;
    FOR(i,1,MAXM) fv = ff[v][i-1];
    G[dep[v]].pb(v);
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa) continue;
        dep[e[i].to] = dep[v] + 1;
        f[e[i].to][0] = v;dfs(e[i].to,v);
    }
}

inline int lca(int x,int y){
    if(dep[x] != dep[y]){
        if(dep[x] < dep[y]) std::swap(x,y),std::swap(dep[x],dep[y]);
        int d = dep[x] - dep[y];
        FOR(i,0,MAXM) if((1<<i)&d) x = fx;
    }
    if(x == y) return x;
    ROF(i,MAXM,0){
        if(fx == fy) continue;
        x = fx,y = fy;
    }
    return fx;
}

LL ans[MAXN];
int a[MAXN],b[MAXN],c[MAXN],top;
// a: point b: dep c: id

inline void Solve(std::vector<int> &v){
    top = 0;LL res = 0;
    FOR(i,0,(int)v.size()-1){
        int x = v[i];
        if(!i) a[++top] = x,b[top] = 0,c[top] = 0;
        else{
            while("Sqytxdy"){
                int l = lca(a[top],x);
                if(b[top] <= dep[l]){
                    a[++top] = x;b[top] = dep[l];c[top] = i;
                    break;
                }
                res -= 1ll(c[top]-c[top-1])b[top];
                --top;
            }
            res += 1ll(c[top]-c[top-1])b[top];
        }
        ans[x] += res;
    }
}

int main(){
    scanf("%d",&n);int root = 0;
    FOR(i,1,n){
        int f;scanf("%d",&f);
        if(f) add(f,i);
        else root = i;
    }
    dep[root] = 1;dfs(root);
    FOR(d,1,n){
        for(auto x:G[d]) ans[x] += ansf[x] + d;
        Solve(G[d]);
        std::reverse(all(G[d]));
        Solve(G[d]);
    }
    FOR(i,1,n) printf("%lld ",ans[i]-dep[i]);puts("");
    return 0;
}