自动搬运

查看原文

来自洛谷，原作者为

	耶梦加得 In the end it doesn't even matter.

搬运于2025-08-24 22:35:58，当前版本为作者最后更新于2022-02-07 19:19:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，这是道构造题废话。其中 50 分的部分分可以用差分约束来做（与正解无关）。

经过实践，我们发现题目给的这个 $j_i$ 相当不友好，不如统统加上 $1$，这样它就代表第一个大于 $x_i+K$ 的数所在位置，这个条件相对比较好转化。

但也还是没那么好想。

我们建立一棵有 $n+1$ 个节点的树，对于每个节点，与父亲 $j_i+1$ 连一条边。易知根为 $n + 1$。

这是有多经费不足才画出这种东西（恼）

由于 $j_i$ 不降，可以发现层次高（即靠近根节点，见图）的节点编号一定大于层次低的节点。并且 $j_i+1$ 层次恰好比 $i$ 大 $1$ 还是废话。

又根据构造条件，$x[j_i+1]$ 应当大约比 $x[i]$ 大 $K$。由此可以猜测每个节点权值为 $d[i] * K + x'(0 \le x' < K)$。

接下来确定 $x'$ 如何赋值。首先我们对于同一层的节点，按照编号从大到小考虑，由于加边顺序从小到大，用链式前向星可以自然地实现这一点（当然 vector 也无非就是倒序循环的事情）。

我们要使得同一层排在后面的节点，$x'$ 都小于它的任意子节点，与此同时，它自己的 $x'$ 要大于它的任意儿子。

自己的孩子归自己管，别人管不着

我们发现 $dfs$ 序完美地不符合这个条件。于是我们令 $x' = K - dfn[i]$。（逃

（官方样例解释实在太丑，不放了）

由于 $x' \ge 0$，令 $K \ge n + 1$ 即可。不过要注意规定的 $x_i$ 范围。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#define miu 100007
using namespace std;
inline int read() {
    register int x = 0; register char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') {x = x * 10 + ch - 48; ch = getchar();}
    return x;
}
struct edge {
    int v, nxt;
}e[miu];
int head[miu], eid;
inline void insert(int x, int y) {
    e[++eid].v = y; e[eid].nxt = head[x]; head[x] = eid;
}
int ans[miu], d[miu], bonus, n, k;
void dfs(int x) {
    ans[x] = bonus--;
    for(int i = head[x]; i; i = e[i].nxt) {
        int to = e[i].v;
        d[to] = d[x] + 1;
        dfs(to);
    }
}
int suc;
signed main() {
    n = read(); k = n + 2; bonus = n + 1;
    for(int i = 1; i <= n; ++i) {
        suc = read(); insert(++suc, i);
    }
    dfs(n + 1);
    printf("%d\n", k);
    for(int i = 1; i <= n; ++i) {
        printf("%lld\n", 1ll * k * (d[1] - d[i]) + ans[i]);
    }
    return 0;
}