D. Skipping

watersail / 2024-11-13 / 原文

【知难而退】，难以实时维护一个位置对应的下一个位置，那就通过一定的性质避开这个问题
【枚举】到达的最右边的位置
真没想到在这种特殊图上也能卡spfa啊……

点击查看代码

#include <bits/stdc++.h>
using namespace std;
vector<int>a[400005];
vector<int>c[400005];
int val[400005],b[400005];
long long sum[400005],d[400005];
bool v[400005];
/*
queue<int>q;
void spfa()
{
	d[1]=0;
	v[1]=true;
	q.push(1);
	while(q.size())
	{
		int n1=q.front();
		q.pop();
		v[n1]=false;
		for(int i=0;i<a[n1].size();i++)
		{
			if(d[n1]+c[n1][i]<d[a[n1][i]])
			{
				d[a[n1][i]]=d[n1]+c[n1][i];
				if(!v[a[n1][i]])
				{
					v[a[n1][i]]=true;
					q.push(a[n1][i]);
				}
			}
		}
	}
}
*/
typedef pair<long long,int> cc;
priority_queue<cc,vector<cc>,greater<cc> >q; 
void dijkstra()
{
	d[1]=0;
	q.push(make_pair(0,1));
	while(q.size())
	{
		int n1=q.top().second;
		q.pop();
		if(v[n1])
		{
			continue;
		}
		v[n1]=true;
		for(int i=0;i<a[n1].size();i++)
		{
			if(d[n1]+c[n1][i]<d[a[n1][i]])
			{
				d[a[n1][i]]=d[n1]+c[n1][i];
				q.push(make_pair(d[a[n1][i]],a[n1][i]));
			} 
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			a[i].clear();
			c[i].clear();
			d[i]=LLONG_MAX;
			v[i]=false;
		}
		for(int i=1;i<=n;i++)
		{
			cin>>val[i];
			sum[i]=sum[i-1]+val[i];
		}
		for(int i=1;i<=n;i++)
		{
			cin>>b[i];
			if(i>1)
			{
				a[i].push_back(i-1);
				c[i].push_back(0); 
			}
			a[i].push_back(b[i]);
			c[i].push_back(val[i]);
		}
		dijkstra();
		long long ans=0;
		for(int i=1;i<=n;i++)
		{
			ans=max(ans,sum[i]-d[i]);
		}
		cout<<ans<<"\n";
	}
	return 0;
}