loj#2509. 「AHOI / HNOI2018」排列(思維題 set)

題意

題目鏈接

Sol

神仙題Orz

首先不難看出如果我們從\(a_i\)向\(i\)連一條邊，我們會得到以\(0\)為根的樹(因為每個點一定都有一個入度，出現環說明無解)，同時在進行排列的時候需要保證父親節點一定在孩子節點之前出現

接下來考慮直接貪心。對於某些權值很小的點，我們需要讓其儘早出現，同時又要滿足選擇的條件。

那麼我們可以從小的點開始，依次向他的父親合併，並刪除該點(也就是如果父親一但被刪除，那麼這個點立馬被刪除)

下麵的內容抄襲摘抄自這裡

然後直接用set搞一搞

複雜度：\(O(n\log n)\)

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int MAXN = 5e5 + 10, SS = 1e7 + 10;
template<typename A, typename B> inline void chmax(A &x, B y) {
    x = x > y ? x : y;
}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, a[MAXN], fa[MAXN], vis[MAXN], ufa[MAXN];
LL w[MAXN], siz[MAXN];
vector<int> v[MAXN];
struct comp {
    bool operator ()(int x, int y) {
        return w[x] * siz[y] == w[y] * siz[x] ? x < y : w[x] * siz[y] < w[y] * siz[x];
    }
};
int find(int x) {
    return ufa[x] == x ? ufa[x] : ufa[x] = find(ufa[x]);
}
set<int, comp> s;
int dfs(int x) {
    vis[x] = 1;
    for(auto &to : v[x]) {
        if(vis[to] == 1) return 1;
        if(dfs(to)) return 1;
    }
    vis[x] = 2;
    return 0;
}
int main() {
    N = read();
    for(int i = 1; i <= N; i++) {
        fa[i] = read(); 
        v[fa[i]].push_back(i);
    }
    for(int i = 1; i <= N; i++) 
        if(!vis[i]) 
            if(dfs(i)) {puts("-1"); return 0;}
    for(int i = 1; i <= N; i++) w[i] = read(), ufa[i] = i, siz[i] = 1, s.insert(i);
    siz[0] = 1; ufa[0] = 0;
    LL ans = 0;
    for(int i = 1; i <= N; i++) {
        int x = *s.begin(); s.erase(s.begin());
        int f = find(fa[find(x)]);
        if(f) s.erase(f);
        ans += siz[f] * w[x];
        siz[f] += siz[x]; w[f] += w[x]; 
        ufa[x] = f;
        if(f) s.insert(f);
    }
    cout << ans;
    return 0;
}
/*
3
0 1 1
5 7 3
*/