问题分析

原问题中每个节点i指向a[i]，构成功能图。由于a[i]=i的自环点会导致冲突，故采用反向建图（a[i]连边至i），形成外向基环树森林。对基环树，需破环为树后用DP求解；自环点直接设价值为0后DP。

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
vector<int> G[N];
int a[N];
bool vis[N];
ll f[N][2], c[N];

void dp(int x, int rt) {
    vis[x] = 1;
    f[x][1] = c[x];
    f[x][0] = 0;
    for (int y : G[x]) {
        if (y != rt) {
            dp(y, rt);
            f[x][0] += f[y][1];
            f[x][1] += min(f[y][0], f[y][1]);
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        G[a[i]].emplace_back(i);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &c[i]);
    }

    ll ans = 0;
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++) {
        if (vis[i] == 0) {
            int x = a[i], y = i;
            while (x != y) {
                x = a[a[x]];
                y = a[y];
            } // 乌龟兔子算法找环上一点
            y = a[x]; // 环上与x相邻的另一点

            if (a[x] == x) { // 自环点（环长为1）
                c[x] = 0;
                dp(x, x);
                ans += f[x][1];
            } else { // 环长大于1，破环为两棵树，取min
                dp(x, x);
                ll t1 = f[x][1];
                dp(y, y);
                ll t2 = f[y][1];
                ans += min(t1, t2);
            }
        }
    }

    printf("%lld\n", ans);
    return 0;
}