Solution

对于索引，一般会考虑建边。但是本题直接考虑建边较为困难，因为会有自边。考虑到有 $i \leq j_i$ 的线性性质可以建树，又考虑到 $j_i$ 是最大索引，所以我们可以正难则反考虑使用 $j_i+1$ 点，也即第一个 $j>j_i$ 使得 $x_{j} > x_i +K$。

将树建立起来。由于一棵树最大不会超过 $n+1$ 层，所以我们可以构造线性式子 $x_i=d_i \times K + c_i$ 来表示，且 $c_i \in [0,K]$，故可取 $K \geq n+1$。同时，$d_i$ 表示树底到当前位置的高度。

考虑对于这棵树，想要满足题目限制条件需要满足的性质。

• 考虑连边的自身性质。考虑边 $(u,v)$，满足 $v=i,u=j_i+1$。那么一定要有 $x_u-x_v>K$。故必须有 $c_u>c_v$。
• 考虑相同深度的点的性质。对于任意相同深度的点 $u_1<u_2$，必须有 $x_{u_1}\leq x_{u_2}$。实际上，相当于 $c_{u_1} \leq c_{u_2}$（充分条件为 $c_{u_1}<c_{u_2}$）。

这种勾连父子节点和兄弟节点的约束条件很容易想到具有相同性状的 DFS 序，不过若将 DFS 序看成 $c$，那么有 $c_u<c_v$ 且 $c_{u_1} < c_{u_2}$。

那么就好办了。只要得到 DFS 序之后对任意点 $i$ 赋值 $c_i \gets (K-c_i)$。那 $c_{u_1}<c_{u_2}$ 不是不满足了吗？莫慌，在得到 DFS 序的时候枚举子节点的时候倒序就行了，毕竟从高到底都倒序那一定是满足同一深度的所有节点的限制条件的。

Code

表示变量可能略有不同，不过还是可以对应上的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
int dep[100010],dmax;
vector<int> g[100010];
int dfn[100010],tot;
void dfs(int u,int f) {
    dep[u]=dep[f]+1;
    dmax=max(dmax,dep[u]);
    dfn[u]=++tot;
    for(int i=g[u].size()-1,v;i>=0;i--) v=g[u][i],dfs(v,u);
    return ;
}
signed main() {
    cin>>n;
    k=n+1;
    for(int i=1,j;i<=n;i++) {
        cin>>j;
        g[j+1].push_back(i);
    }
    dfs(n+1,n+1);
    cout<<k<<"\n";
    for(int i=1;i<=n;i++) cout<<((dmax-dep[i])*k+k-dfn[i])<<"\n";
    return 0;
}

Conclusion

树上构造题。首先，得找到由限制条件得到的建树的具体内容（可能是限制条件本身，也可能反限制条件，即正难则反）；其次，得根据题目所给的信息进行一定的构造；最后，能根据树上的性质与构造的内容将它们结合起来得到最终要求的。其中，第一步是首先需要思考的，第二步和第三步可以在思考的过程中互相和共同进行，最终完成。