この問題は少し難しいですが、グラフ理論を用いた問題を解き慣れた人ならばすぐにピンと来るテーマを扱っています。

• おそらく参加者の中には、図を書くなどしてこの問題を ad-hoc な考察で解いた方もいると思います。もちろんそれで充分ですが、グラフ理論の知識があるとこの問題の構造を直ちに見抜くことができます。

ここではグラフ理論の言葉を用いて解説していきます。
この問題で与えられている人間関係をグラフの言葉を使って言い換えると次のようになります。

\(N\) 頂点 \(N\) 辺の自己辺を持たない有向グラフ \(G\) がある。各頂点の出次数は \(1\) で、頂点 \(i\) から出る辺は \(X_i\) へ向かっている。

このようにすべての頂点の出次数が \(1\) の有向グラフを Functional Graph と呼びます。 Functional Graph の性質として次のようなものが挙げられます。

Functional Graph の性質

\(G\) の連結成分が \(K\) 個あって \(C_1, C_2, \dots, C_K\) とする。このとき、各連結成分には閉路が \(1\) つだけ存在する。

(証明)
帰納的に証明します。連結成分のサイズが小さい場合は総当たり的に調べれば確認できます。サイズ \(k\) の連結成分について命題が成り立つ時、サイズ \(k+1\) の連結成分について命題が成り立つことを確認します。
連結成分 \(C\) に含まれるすべての頂点の入次数が \(1\) である場合と、そうでない場合で場合分けを行います。

• すべての頂点の入次数が \(1\) の場合
  全ての頂点の出次数・入次数がともに \(1\) のグラフは 置換グラフ(順列グラフ) と呼ばれるグラフです。\(k+1\) 頂点の連結な置換グラフはサイズ \(k+1\) の閉路をなすので、閉路の個数は \(1\) 個になります。
• そうでない場合
  入次数が \(1\) でない頂点が含まれている場合、グラフ上の頂点の入次数の平均は \(1\) なので、入次数 \(0\) の頂点が存在します。その頂点を \(n\) とします。
  \(C\) から \(n\) および \(n\) から伸びる辺を取り除いたグラフを \(C'\) とします。\(C'\) は連結なので、帰納法の仮定から閉路が \(1\) 個であることが確認できます。

問題文に戻ります。 \(G\) の各連結成分を \(C'_1, C'_2, \dots,C'_K\) とします。各連結成分に対して個別に問題が解ければよいです。\(G\) の連結成分を \(1\) つ取って \(H\) とすると、\(H\) の最適解は次のようになります。

\(H\) に含まれる閉路を構成する頂点を \(v_1 \to v_2 \to \dots \to v_m \to v_1\) とする。このとき、人 \(v_1,v_2,\dots,v_m\) の中のちょうど 1 人が不満度が正になるのが最適である。 すなわち

\[\min(C_{v_1}, \dots, C_{v_m})\ \ \ (\ast)\]

が \(H\) の答えとなる。

正当性は \((\ast)\) が上界にも下界にもなることを確認すれば証明できます。\((\ast)\) が下界であるのは \(v_1,v_2,\dots,v_m\) がサイクルをなすことから示せます。また、\((\ast)\) が上界なのは実際に不満度が \((\ast)\) になるグラフが常に構築できることからいえます。

実際に答えを求めるには、Functional Graph の閉路の部分をすべて列挙できればよいです。これは Union Find を用いれば \(\mathrm{O}(N \alpha(N))\) の計算量で行うことができて、これは AC するのに十分高速です。

• 実装例 (C++)

#include <iostream>
#include <vector>
using namespace std;

#include "atcoder/dsu.hpp"

int main() {
  int N;
  cin >> N;
  vector<int> X(N), C(N);
  for (auto& x : X) cin >> x, --x;
  for (auto& x : C) cin >> x;
  atcoder::dsu uf(N);
  long long ans = 0;
  for (int i = 0; i < N; i++) {
    if (uf.same(i, X[i]) == false) {
      uf.merge(i, X[i]);
      continue;
    }
    int cur = C[i], v = i;
    do {
      v = X[v];
      cur = min(cur, C[v]);
    } while (v != i);
    ans += cur;
  }
  cout << ans << "\n";
}