警告

LHn 不许看！

警告

LHn 不许看！

警告

LHn 不许看！

题意

有一棵以 $1$ 为根的树，点有点权 $w_i$ 和目标 $a_i$。给定数 $c$。

可以进行如下操作任意次：选择 $u,v$ 满足 $u$ 为 $v$ 的父结点，交换 $w_u, w_v$ 然后把 $w_u$ 加上 $c$，$w_v$ 减去 $c$。

最小化 $\displaystyle\sum_{i=1}^{n} |w_i - a_i|$。

这道题需要转换视角。我们不再关注每一个点如何映射到点权，而是关注每一个点权如何映射到点。

注意到点权每次上移必定 $+c$，每次下移必定 $-c$。因此，将点权 $w$ 从 $u$ 移到 $v$，它一定变为 $w + c (d_u - d_v)$，其中 $d_u$ 为 $u$ 的深度。

不难证明树上交换一定可以交换到每个排列（每次到位一个叶子，然后变成子问题），于是答案相当于

$$\min_{p \in \mathscr{P}} \sum_{i=1}^{n} |w_{p_i} + c d_{p_i} - c d_i - a_i| \xlongequal{\text{分离变量换元}} \min_{p \in \mathscr{P}} \sum_{i=1}^{n} |s_{p_i} - t_i|$$

这是经典问题，对 $s_i$ 和 $t_i$ 分别排序即可，调整可证。

Code（未验证）

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

typedef long long ll;
const int maxn=1e5+10;
ll w[maxn], a[maxn];
int fa[maxn];
vector<int> G[maxn];
ll dep[maxn], s[maxn], t[maxn];

void dfs(int u) {
    dep[u] = dep[fa[u]] + 1;
    for (int v: G[u]) {
        if (v == fa[u]) {
            continue;
        }
        dfs(v);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    ll n, c; cin >> n >> c;
    for (int i=1; i<=n; i++) {
        cin >> w[i];
    }
    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }
    for (int i=2; i<=n; i++) {
        cin >> fa[i];
        G[fa[i]].push_back(i);
    }
    
    dfs(1);
    
    for (int i=1; i<=n; i++) {
        s[i] = w[i] + c * dep[i];
        t[i] = a[i] + c * dep[i];
    }
    
    sort(s+1, s+n+1);
    sort(t+1, t+n+1);
    
    ll ans = 0;
    for (int i=1; i<=n; i++) {
        ans += abs(s[i] - t[i]);
    }
    cout << ans;
    
    return 0;
}

版权所有

版权归属：Phantom-Bird

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)

查看此页源代码

贡献者: Phantom-Bird

上一页最小值、最大值与绝对值

下一页反射计数