ABC 略

D

这个过程一定是由1向后跳的过程中穿插有几次向前一步一步走。直到跳到一个位置后再把前面所有没有走过的位置倒序走一遍。总分就等于最大位置的前缀和-前面所有起跳位置和。前缀和固定我们只需要求到每个位置的最小起跳和即可。对于这个向后跳和向前走的过程我们可以用一张有向图图抽象，具体而言，对于i和i+1连边，边权为0，对于每个位置i，如果b[i]>i那么i到b[i]连边，边权为a[i]。如果出现相同的b[i]可能走重的情况有i和i+1无边权的边可以规避。那么每个位置的最小起跳和就是1到这个位置的最短路。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e5+10;
int T,n,a[N],b[N],d[N],v[N],ans;
int ver[N*2],edge[N*2],head[2*N],Next[N*2],tot;
void init()
{ans=tot=0;for(int i=1;i<=2*n;i++)ver[i]=edge[i]=Next[i]=head[i]=0;
}
void add(int x,int y,int z)
{ver[++tot]=y,edge[tot]=z;Next[tot]=head[x],head[x]=tot;
}
void dij()
{priority_queue< pair<int,int> >q;for(int i=1;i<=n;i++)d[i]=4e14,v[i]=0;d[1]=0;q.push(make_pair(0,1));while(q.size()){int x=q.top().second;q.pop();v[x]=1;for(int i=head[x];i;i=Next[i]){int y=ver[i],z=edge[i];if(d[y]>d[x]+z){d[y]=d[x]+z;q.push(make_pair(-d[y],y));}}}
}
void solve()
{cin>>n;init();for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];for(int i=1;i<n;i++){add(i+1,i,0);if(b[i]>i) add(i,b[i],a[i]);}dij();int s=a[1];for(int i=2;i<=n;i++){s+=a[i];ans=max(ans,s-d[i]);}cout<<max(ans,a[1])<<endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie();cout.tie();cin>>T;while(T--) solve();
}