题解：P8098 [USACO22JAN] Tests for Haybales G

· · 题解

这种题多积累就会做了。

adhoc + 充分发挥人类智慧。

但是好像这道题啥都用不了（？）

差分约束是可以得到 50\% 的数据点的。

题目中给的东西是比较像树的，所以可以考虑建一棵树来看看。

但是单按照题目条件建出的并不是一棵树，所以考虑将每个值加 1。

所以现在的题目条件就是对于一个点 u, 这个点的父亲就是它第一个大于 x_u + K 这个值的。

于是，我们可以将 x_i = (dep_1-dep_i) \times k，同时，原本题目明面上的要求也被满足了。

我们将 x_i 重新定义为 x_i = (dep_1-dep_i) \times k + p'。

现在，我们考虑求 p'。

我们现在要满足以下条件：

所以可以得到了：

(dep_{fath}-dep_i) \times k < p_{fath}' - p_i'

因为 dep_{fath}-dep_i = -1，所以可以得到的是 p_{fath}' - p_i' < k。

很容易想到可以使用 dfs 序来满足条件。

但是呢，还是错了，这回就比较显然了，你会 dfn_{fath} < dfn_{u} 的，这就很不对了，我们要满足的条件更远了。

怎么办呢？

考虑正不行就反着来，所以直接将 dfn_u 变为 k-dfn_u 就行了。

最后让 k 最够大就行了。

然后就做完了。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5+10;
const int M = 4e5+10;

int n, k;

int cnt, head[N];
int to[M], nxt[M];

int t, dfn[N];
int dep[N];

void connect(int u, int v) {
    cnt++, nxt[cnt] = head[u];
    head[u] = cnt, to[cnt] = v;
}

void dfs(int u, int from) {
    dep[u] = dep[from] + 1;
    dfn[u] = ++t; dfn[u] = k - dfn[u];
    for (int i = head[u];i;i=nxt[i]) {
        int v = to[i];
        if (v == from) continue;
        dfs(v, u);
    }
}

int fath;

signed main() {
    cin >> n; k = 1e9;
    for (int i = 1;i<= n;i++) {
        cin >> fath; fath++;
        connect(fath, i), connect(i, fath);
    } dep[0] = -1;
    dfs(n + 1, 0);
    cout << k << endl;
    for (int i = 1;i<= n;i++) {
        cout << k * (dep[1] - dep[i]) + dfn[i] << "\n";
    }
    return 0;
}