P8098 [USACO22JAN] Tests for Haybales G

· · 题解

首先，这是道构造题废话。其中 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;
}