题目大意：

n ( ≤ 1 e 5 ) n(\le1e5) n(≤1e5)件商品，第 i i i件商品价格为 p [ i ] p[i] p[i]，可以用以下两种折扣中的一种：

• 得到 d [ i ] d[i] d[i]的折扣，价格变为 p [ i ] − d [ i ] p[i]-d[i] p[i]−d[i]
• 原价 p [ i ] p[i] p[i]购买，免费获得 f [ i ] f[i] f[i]物品

解题思路：

• f [ i ] → i f[i]\rightarrow i f[i]→i连边，那么就构成了基环树（树上有且仅有一个环）森林

• 对于基环树常见的套路就是：先处理连接环的树，再拆环为链，最后考虑拆除部分的情况

• 先看普通树应该如何处理：设 d p [ i ] [ 0 ] dp[i][0] dp[i][0]子树 i i i的最小费用， d p [ i ] [ 1 ] dp[i][1] dp[i][1]表示以第二种优惠购买商品 i i i的最小费用（免费拥有其父亲）
  d p [ i ] [ 1 ] = p [ u ] + ∑ v ∈ s o n [ u ] d p [ v ] [ 0 ] d p [ i ] [ 0 ] = m i n ( p [ u ] − d [ u ] + ∑ v ∈ s o n [ u ] d p [ v ] [ 0 ] , m i n v ′ ∈ s o n [ u ] ( d p [ v ′ ] [ 1 ] + ∑ v ∈ s o n [ u ] , v ! = v ′ d p [ v ] [ 0 ] ) ) dp[i][1]=p[u]+\sum_{v\in son[u]}dp[v][0] \\ dp[i][0]=min(p[u]-d[u]+\sum_{v\in son[u]}dp[v][0],min_{v'\in son[u]}(dp[v'][1]+\sum_{v\in son[u],v!=v'}dp[v][0])) dp[i][1]=p[u]+v∈son[u]∑​dp[v][0]dp[i][0]=min(p[u]−d[u]+v∈son[u]∑​dp[v][0],minv′∈son[u]​(dp[v′][1]+v∈son[u],v!=v′∑​dp[v][0]))

• 对于环，先将其拆成链，设环上结点个数为 m m m， c i r [ i ] cir[i] cir[i]为链上第 i i i个结点对应的是原图中哪个结点：
  g [ i ] [ 1 ] = d p [ c i r [ i ] ] [ 1 ] + g [ i − 1 ] [ 0 ] g [ i ] [ 0 ] = m i n ( d p [ c i r [ i ] ] [ 0 ] + g [ i − 1 ] [ 0 ] , g [ i − 1 ] [ 1 ] + ∑ v ∈ s o n [ c i r [ i ] ] d p [ v ] [ 0 ] ) g[i][1] = dp[cir[i]][1]+g[i-1][0] \\ g[i][0]=min(dp[cir[i]][0]+g[i-1][0],g[i-1][1]+\sum_{v\in son[cir[i]]}dp[v][0]) g[i][1]=dp[cir[i]][1]+g[i−1][0]g[i][0]=min(dp[cir[i]][0]+g[i−1][0],g[i−1][1]+v∈son[cir[i]]∑​dp[v][0])

• 接下来对于拆除部分，再分两种情况考虑第 m m m个结点是否对第 1 1 1个结点有赠送来初始化：
  有 赠 送 ： g [ 1 ] [ 0 ] = ∑ v ∈ s o n [ c i r [ 1 ] ] d p [ v ] [ 0 ] , g [ 1 ] [ 1 ] = d p [ c i r [ 1 ] ] [ 1 ] 无 赠 送 ： g [ 1 ] [ 0 ] = d p [ c i r [ 1 ] ] [ 0 ] , g [ 1 ] [ 1 ] = d p [ c i r [ 1 ] ] [ 1 ] 有赠送：g[1][0]=\sum_{v\in son[cir[1]]}dp[v][0], g[1][1]=dp[cir[1]][1] \\ 无赠送：g[1][0]=dp[cir[1]][0],g[1][1]=dp[cir[1]][1] 有赠送：g[1][0]=v∈son[cir[1]]∑​dp[v][0],g[1][1]=dp[cir[1]][1]无赠送：g[1][0]=dp[cir[1]][0],g[1][1]=dp[cir[1]][1]

AC代码：

#include <bits/stdc++.h>
#define ft first
#define sd second
#define pb push_back
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) //不能跟puts混用
#define seteps(N) fixed << setprecision(N)
#define endl "\n"
const int maxn = 1e5 + 10;
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f3f3f3f;
int n, cntc, f[maxn], cir[maxn];
ll sdp[maxn]; //sdp[i]存储的是以i为父节点的j的dp[j][0]总和
ll p[maxn], d[maxn], dp[maxn][2], g[maxn][2];
vector <int> G[maxn];
int vis[maxn];
ll ans = 0;
void solve2(int u) { //树上问题
    ll res = 0;
    dp[u][1] = p[u];
    dp[u][0] = p[u] - d[u];
    for (auto v : G[u]) {
        if (vis[v] == 2) continue;
        solve2(v);
        res += dp[v][0];
    }
    dp[u][1] += res, dp[u][0] += res;
    sdp[u] = res;
    for (auto v : G[u]) {
        if (vis[v] == 2) continue;
        vis[v]++;
        dp[u][0] = min(dp[u][0], res - dp[v][0] + dp[v][1]);
    }
}
void solve1(int id) { //
    cntc = 0;
    while (!vis[id]) vis[id]++, id = f[id];
    while (vis[f[id]] != 2) { //处理环上的点
        vis[f[id]]++;
        cir[++cntc] = id;    
        id = f[id];
    }
    for (int i = 1; i <= cntc; i++) {
        solve2(cir[i]); //解决以cir[i]为根的树上问题
    }
    // 处理环上问题：拆环为链
    /* 第一个点不是由最后一个点赠送 */
    ll res = inf;
    g[1][0] = dp[cir[1]][0], g[1][1] = dp[cir[1]][1];
    for (int i = 2; i <= cntc; i++) {
        g[i][1] = dp[cir[i]][1] + g[i - 1][0];
        g[i][0] = min(dp[cir[i]][0] + g[i - 1][0], g[i - 1][1] + sdp[cir[i]]);
    }
    res = min(res, g[cntc][0]);
    /* 第一个点是由最后一个点赠送 */
    g[1][0] = sdp[cir[1]], g[1][1] = dp[cir[1]][1];
    for (int i = 2; i <= cntc; i++) {
        g[i][1] = dp[cir[i]][1] + g[i - 1][0];
        g[i][0] = min(dp[cir[i]][0] + g[i - 1][0], g[i - 1][1] + sdp[cir[i]]);
    }
    res = min(res, g[cntc][1]);
    ans += res;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 1; i <= n; i++) cin >> d[i];
    for (int i = 1; i <= n; i++) cin >> f[i], G[f[i]].pb(i);
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) 
            solve1(i);
    }
    cout << ans << endl;
    return 0;
}