[HNOI2018] 排列

Description

给定 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 以及 $n$ 个整数 $w_1,w_2,\cdots,w_n$ 。称 $a_1,a_2,\cdots,a_n$ 的一个排列 $a_{p_1},a_{p_2},\cdots,a_{p_n}$ 为一个合法排列当且仅当该排列满足：对于任意的 $k$ 和任意的 $j$ ，如果 $j\leq k$ ，那么 $a_{p_j}\ne p_k$ 。定义一个合法排列的权值为 $w_{p_1}+2w_{p_2}+\cdots + nw_{p_n}$ 。
你需要求出所有合法排列中的最大权值。如果不存在，输出 -1 。
$n\leq 5\times 10^5,a_i\in[0,n],\sum w_i\leq 1.5\times 10^{13}$

Solution

这道题好神啊。
首先给出的这个限制不是很直观，我们转化一下来方便理解。
现在有一个空序列 p[] ，我们往这里面依次加 $1\sim n$ ，要求加完以后成了一个排列。
当加到第 $i$ 个的时候，此时 $p_i$ 确定了，$a_{p_i}$ 确定了，如果我们还没有将 $a_{p_i}$ 放入序列中，就意味着必然存在一个 $k$ ，使得 $a_{p_i} = p_k \cap i\leq k$ 。这是不合法的。
得出结论：最终序列中 $a_i$ 一定要放在 $i$ 前面。这与序列是否合法互为充要条件。
转化了限制以后题目变得好做了一些。我们让这个限制更加直观一点，把限制上图。
令 $a_i$ 是 $i$ 的父亲，则原图每个点只有一个入度，要么是一个有向无环树，要么有环。有环自然就是无解，而在有向无环树中，每一个拓扑序都是一个合法排列。

所以拓扑序的第 $T$ 位（假设为 $x$）的权值是 $T\times w_{p_T}=T\times w_x$ 。也就是在树上从根开始遍历整棵树，每棵树的点权为 $w_i$ ，第一次经过的时刻为 $T_i$ ，那么贡献就是

$\sum_{i=1}^{n}w_iT_i$

接下来我们需要让贡献最大化。考虑目前的 $w_u$ 最小值的点 $u$ ，若 $u$ 的父亲被选，那么 $u$ 一定是紧接着被选，于是我们可以合并这两个点，并重新赋贡献，这个贪心较显然。扩展这个贪心至整棵树的关键之处在于如何重新赋贡献。考虑某个时刻，点 $p$ 下挂了两个点 $u$ 和 $v$ 。$u$ 和 $v$ 目前均代表一个序列（ p 序列的一部分 ），我们是先放 $u$ 还是先放 $v$ 呢？在贪心中，抽象化两个物品，并直接比较两种不同方法的贡献是一种不错的方法。令 $\mathcal{W}_u$ 和 $\mathcal{W}_v$ 分别是 $u$ 和 $v$ 代表的序列的 $w$ 之和，$\mathcal{S}_u$ 和 $\mathcal{S}_v$ 分别是 $u$ 和 $v$ 代表的序列的长度 ，那么两种情况贡献的差值为：

$w_{u\rightarrow v} - w_{v\rightarrow u} = \mathcal{S}_u\times \mathcal{W}_v - \mathcal{S}_v\times \mathcal{W}_u$

于是维护好各自的 $\mathcal{S}$ 和 $\mathcal{W}$ 就可以利用堆来实现贪心了。

复杂度 $\mathcal{O}(n\log_2 n)$ 。

Code

const int N = 5e5 + 5;
using namespace std;
int n, tot;
int f[N], fa[N], sz[N], vis[N];
long long v[N];
vector<int> c[N];
struct node{
    int u, sz;
    long long sv;
    bool operator < (const node &b) const{
        return 1ll * sz * b.sv < 1ll * sv * b.sz;
    }
};
void dfs(int p){
    ++tot, vis[p] = 1;
    for(auto u:c[p])
        if(!vis[u]) dfs(u);
}
int Find(int x){
    return x == f[x] ? x : f[x] = Find(f[x]);
}
int main(){

    r(n);
    for(int i = 1; i <= n; ++i) 
        r(fa[i]), c[fa[i]].push_back(i);
    for(int i = 1; i <= n; ++i) 
        r(v[i]);
    dfs(0);
    if(tot <= n) return puts("-1"),0;
    for(int i = 0; i <= n; ++i)
        f[i] = i, sz[i] = 1;
    priority_queue<node>q;
    for(int i = 1; i <= n; ++i)
        q.push((node){i, 1, v[i]});
    long long ans = 0;
    while(!q.empty()){
        node now = q.top(); q.pop();
        int u = Find(now.u);
        if(sz[u] != now.sz) continue;
        int anc = f[u] = Find(fa[u]);
        ans += 1ll * v[u] * sz[anc];
        sz[anc] += sz[u], v[anc] += v[u];
        if(anc) q.push((node){anc, sz[anc], v[anc]});
    }
    w(ans);
    return 0;
}