This problem is a bit difficult, but it treats the theme that strikes those who are used to graph theory.

• Some of you may have succeeded in solving this problem by drawing diagrams and making ad-hoc consideration. Of course that is great, but the insight into graph theory enables you to spot the structure of this problem at once.

In this problem, we use the terms of graph theory to describe the problem.
The relationships of the people given in this problem can be rephrased using terms of graph theory as follows:

There are a directed graph \(G\) with \(N\) vertices and \(N\) edges. The outdegree of each vertex is \(1\); the edge incident from Vertex \(i\) goes to \(X_i\).

Like this, a directed graph of which the outdegree of every vertex is \(1\) is called a Functional Graph. One of the properties of Functional Graph is as follows:

A property of a Functional Graph:

Suppose that \(G\) has \(K\) connected components, \(C_1, C_2, \dots, C_K\). Then, each connected component has exactly one cycle.

(Proof)
We prove it by induction. For a sufficiently small sized connected component, we can exhaustively enumerate all possible cases. We will now assert that, if the proposition holds for a connected component of size \(k\), it also holds for that of size \((k+1)\).
We will divide into cases depending on whether the indegree of every vertex is \(1\) or not.

• If the indegree of every vertex is \(1\):
  A graph of which every vertex has one ingoing and outgoing edge is called a permutation graph. Since a \((k+1)\)-vertex permutation graph forms a cycle of size \((k+1)\), it has exactly one cycle.
  
• Otherwise
  If the graph has a vertex with indegree other than \(1\), then there exists a vertex with an indegree of \(0\), since the average of indegrees of the verteices is \(1\). Let \(n\) be such a vertex.
  Let \(C\) be a graph after removing \(n\) and the edges going from \(n\). Since \(C'\) is connected, by the assumption of the induction, we can confirm that it has exactly one cycle.

Let’s go back to the original problem. Let \(C_1, C_2, \dots,C_K\) be the connected components of \(G\). It is sufficient to solve the problem for each connected component. Let \(H\) be a connected component of \(G\), then the optimal solution for \(H\) is obtained as follows.

Let \(v_1 \to v_2 \to \dots \to v_m \to v_1\) be the vertices forming the cycle of \(H\). Then, it is optimal when exactly one of People \(v_1,v_2,\dots,v_m\) has a positive amount of frustration. In other words, the answer for \(C\) is:

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

This can be justified by the fact that \((\ast)\) is both the upper and the lower bound. \((\ast)\) is the lower bound because \(v_1,v_2,\dots,v_m\) forms a cycle; \((\ast)\) is the upper bound because we can actually construct a graph in which the total frustration equals \((\ast)\).

In order to find the answer, it is sufficient to enumerate all the cycles in the Functional Graph. With Union Find, this can be achieved in a total of \(\mathrm{O}(N \alpha(N))\) time, which is fast enough to get AC (Accepted).

• Sample code (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";
}