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();
}