[ 牛客网暑期ACM多校训练营(第二场) ] B Discount

        题目大意：有n个物品，第i个物品的价格为\(p_i\)，对每个物品，有两种优惠策略，可以选择其一：

        1.购买该物品可以得到\(d_i\)元的打折（即购买该物品只需\(p_i - d_i\)元）。

        2.购买该物品后可以免费购买第\(f_i\)个物品。

        求购买n个物品的最小花费。其中\(1 \leq n \leq 10^5 , 0 \leq d_i \leq p_i \leq 10^9 , 1 \leq f_i \leq n\)。

        题解：将每个物品i与物品\(f_i\)连边，可以得到一个基环外向树，然后我们要做的事情就是在这上面做DP。把环拿出来，剩下的就是一堆树，分原价购买以及（免费或打折购得）两种状态进行DP，在环上DP时再记录DP的第一个物品的状态。

#include <bits/stdc++.h>
using namespace std;
const long long inf=~0ull>>2;
const int maxn=1e5+10;

int head[maxn],nxt[maxn<<1],E[maxn<<1],Ecnt;
int DFN[maxn],Low[maxn],ID[maxn],GQ[maxn],cnt,GQN,Index;
long long F[maxn][2],G[maxn][3][2];
int p[maxn];
int d[maxn];
int f[maxn];
int n;
long long ans;

void Add_Edge(int x,int y)
{
	nxt[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;
	nxt[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;
}

int Q[maxn],Inq[maxn],qtop;
void Tarjan(int x)
{
	DFN[x]=Low[x]=++Index;
	Q[++qtop]=x;
	Inq[x]=1;
	if (!DFN[f[x]]) Tarjan(f[x]),Low[x]=min(Low[x],Low[f[x]]);
	else if (Inq[f[x]]) Low[x]=min(Low[x],DFN[f[x]]);
	if (DFN[x]==Low[x])
	{
		cnt++;
		while (Inq[x])
		{
			int u=Q[qtop--];
			Inq[u]=0;
			ID[u]=cnt;
		}
	}
}

void DFS(int x)
{
	ID[x]=-1;
	GQ[++GQN]=x;
	for (int i=head[x];i;i=nxt[i]) if (!ID[E[i]]) DFS(E[i]);
}

void Solve_Subtree(int x)
{
	for (int i=head[x];i;i=nxt[i]) if (ID[E[i]]!=ID[x] && f[x]!=E[i]) Solve_Subtree(E[i]);
	long long fmin=0,fmin_one=0;
	for (int i=head[x];i;i=nxt[i]) if (ID[E[i]]!=ID[x] && f[x]!=E[i])
	{
		if (F[E[i]][1]<=F[E[i]][0]) fmin_one=1,fmin+=F[E[i]][1];
		else fmin+=F[E[i]][0];
	}
	F[x][1]=fmin+p[x];
	if (fmin_one) F[x][0]=fmin;
	else {
		F[x][0]=inf;
		for (int i=head[x];i;i=nxt[i]) if (ID[E[i]]!=ID[x] && f[x]!=E[i])
			F[x][0]=min(F[x][0],fmin-F[E[i]][0]+F[E[i]][1]);
	}
	F[x][0]=min(F[x][0],fmin+p[x]-d[x]);
}

long long Solve_Circle(int x)
{
	if (f[x]==x) return min(F[x][0],F[x][1]);
	int last=x,sx=x;
	G[x][0][0]=F[x][1]-p[x];
	G[x][0][1]=inf;
	G[x][1][0]=F[x][0];
	G[x][1][1]=inf;
	G[x][2][1]=F[x][1];
	G[x][2][0]=inf;
	for (x=f[x];x!=sx;last=x,x=f[x])
	{
		for (int j=0;j<3;j++)
		{
			G[x][j][0]=min(G[last][j][1]+F[x][1]-p[x],min(G[last][j][0],G[last][j][1])+F[x][0]);
			G[x][j][1]=min(G[last][j][0],G[last][j][1])+F[x][1];
		}
		if (f[x]==sx)
		{
			long long res=inf;
			res=min(G[last][0][0],G[last][0][1])+F[x][1];
			res=min(res,G[x][1][0]);
			res=min(res,G[x][1][1]);
			res=min(res,G[x][2][0]);
			res=min(res,G[x][2][1]);
			return res;
		}
	}
	return 0;
}

long long Solve()
{
	if (GQN==1) return p[GQ[1]]-d[GQ[1]];
	int Cir_ID=0;
	for (int i=1;i<=GQN;i++) if (ID[GQ[i]]==ID[f[GQ[i]]]) Cir_ID=ID[GQ[i]];
	for (int i=1;i<=GQN;i++) if (ID[GQ[i]]==Cir_ID) Solve_Subtree(GQ[i]);
	for (int i=1;i<=GQN;i++) if (ID[GQ[i]]==Cir_ID)
		return Solve_Circle(GQ[i]);
	return 0;
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&p[i]);
	for (int i=1;i<=n;i++) scanf("%d",&d[i]);
	for (int i=1;i<=n;i++) scanf("%d",&f[i]),Add_Edge(i,f[i]);
	for (int i=1;i<=n;i++) if (!DFN[i])
	{
		cnt=GQN=Index=0;
		DFS(i);
		for (int j=1;j<=GQN;j++) if (!DFN[GQ[j]]) Tarjan(GQ[j]);
		ans+=Solve();
	}
	printf("%lld\n",ans);
	return 0;
}