Problem

题意：第 $i$ 个数一定要放在第 $a_i$ 个数的前面。

Solution

这整个题目都太神奇了。

神奇的题意，神奇的贪心，神奇的计算贡献。

建议去找 pipiboss 的题解，结合 luogu 的第一篇题解查看。

太神奇了。

// Code by ajcxsu
// Problem: permutation

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

const int N=5e5+10;
typedef long long ll;
struct Node { ll w; int s, id; } nd[N]; 
bool operator <(const Node &a, const Node &b)  {
    return a.w*b.s==b.w*a.s?a.id<b.id:a.w*b.s<b.w*a.s;
}
Node operator +=(Node &a, const Node &b) {
    a.w+=b.w, a.s+=b.s;
    return a;
}
set<Node> s;

int Fa[N];
int Find(int x) { return Fa[x]?Fa[x]=Find(Fa[x]):x; }
bool Union(int a, int b) {
    int af=Find(a), bf=Find(b);
    if(af==bf) return false;
    return Fa[af]=bf, true;
}
int fa[N];
char vis[N];

int h[N], to[N], nexp[N], in[N], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, in[b]++, p++; }

int n;
bool topsort() {
    queue<int> qu;
    for(int i=0;i<=n;i++) if(!in[i]) qu.push(i);
    while(!qu.empty()) {
        int na=qu.front(); qu.pop();
        for(int u=h[na];u;u=nexp[u]) {
            in[to[u]]--;
            if(!in[to[u]]) qu.push(to[u]);
        }
    }
    for(int i=0;i<=n;i++) if(in[i]) return false;
    return true;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin>>n;
    ll w;
    for(int i=1;i<=n;i++) cin>>fa[i], ins(fa[i], i);
    for(int i=1;i<=n;i++) cin>>w, s.insert(nd[i]={w, 1, i});
    if(!topsort()) cout<<-1<<endl, exit(0); // 没找到好的方法判无解。
    Node na;
    ll ans=0;
    nd[0].s=1; // 注意
    while(!s.empty()) {
        na=*s.begin(), s.erase(s.begin());
        fa[na.id]=Find(fa[na.id]);
        if(vis[fa[na.id]]) fa[na.id]=0; // 这个得注意一下
        ans+=nd[fa[na.id]].s*na.w; // 这里是最神奇的。保证在之后加入，又保证与整体时间相匹配。
        if(fa[na.id]) {
            Union(na.id, fa[na.id]);
            s.erase(nd[fa[na.id]]), nd[fa[na.id]]+=na;
            s.insert(nd[fa[na.id]]);
        }
        else vis[na.id]=1, nd[0].s+=na.s; // 注意
    }
    cout<<ans<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-hnoi-2018-permutations.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆