https://codeforces.com/contest/2024/problem/D
脑子抽了觉得最短路算法不能处理带环图，于是记下该题做法。实际上是存在负环图，最短路不存在（无限小）。
floyd和bellman—fold可以处理任意图，并能检测负环。
Dijkstra不能处理带负权图。

对于该题，如果决定在某个点不再跳过，则可获得该位置的前缀和-跳过的问题。容易想到建图，但是下一步正向思考求获得的最大分数感觉只能爆搜，而反向思考我们可以求到达i位置的最少跳过分数，进而在i位置产生一个解preA[i]-dist[i]，然后对所有位置求一个max。建图：i到i-1，代价为0；i到b[i]，代价为a[i]，表示跳过这个问题会受到a[i]的”惩罚”。

#include<bits/stdc++.h>
#define LOCAL//delete when submit!!!!!!
#define MULTI_TEST

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

vector<vector<pll>> g;
int n;
vector<ll> a,b,preA;

vector<ll> dist;
vector<bool> vis;

void solve(){
    cin>>n;
    a.resize(n+1),b.resize(n+1),preA = a;

    vis.assign(n+1,false),dist = vector<ll>(n+1,1e18);

    g = vector<vector<pll>>(n+1);
    for(int i=1;i<=n;i++) cin>>a[i],preA[i]=a[i]+preA[i-1];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++){
        g[i].push_back({i-1,0});
        g[i].push_back({b[i],a[i]});
    }
    auto dijkstra = [&](){
        dist[1] = 0;
        priority_queue<pll,vector<pll>,greater<pll>> pq;
        pq.push({dist[1],1});
        while(!pq.empty()){
            auto [d,u] = pq.top(); pq.pop();
            if(vis[u]) continue;
            vis[u] = true;
            for(auto &[v,w]:g[u]){
                if(dist[v]>dist[u]+w){
                    dist[v] = dist[u]+w;
                    pq.push({dist[v],v});
                }
            }
        }
    };
    dijkstra();
    ll ans = 0;
    for(int i=1;i<=n;i++){
        ans = max(ans,preA[i]-dist[i]);
    }
    cout<<ans<<endl;
}

int main(){     
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}