题目传送门

题意简述

要从 $u$ 去到 $v$ 且负重不能超过路程中道路的权值，但某些城市中会有列车，列车不限重，每去到一个 $v$ 就会完成一个卖出或买入的交易，求卖出的最大值。

方法分析

其实这道题跟 P1967 十分类似，只不过加了一个无限重的列车。

我们可以将有列车的两个点间再加一个权值为无穷大的边，这样就可以解决问题啦。

然后使用 kruskal 生成一颗最大生成树，求出点与点之间的边值的最小值，使用 lca 或者是树剖都行，我这里选择使用 lca。

最后求答案时，如果当前是买入直接全部买下就行，先不需要考虑会不会超重，等到卖出时再与路程中限重的最小值比较，如果必最小值大了，就像时间回溯一样，回到过去把多余的扔掉就行。

整个题就搞定了，还是很容易想到的。

还有一个重点就是一定要开 $longlong$！

初始值也要赋 $longlong$ 的极限值！

本人因此调了两个小时，给个关注安慰一下吧 呜呜呜。

Code

最后贴上代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn=300000+10;
const ll INF=9223372036854775807;
struct node{ll u;ll v;ll w;}arr[maxn];
bool cmp(node a,node b){
	return a.w>b.w;
}
struct edge{ll x;ll p;};
vector<edge> vt[maxn];
ll a[maxn];
ll b[maxn];
ll c[maxn];
ll money;
ll pre[maxn];
ll p,n,m,q;
ll find(ll x){
	if(pre[x]==x) return x;
	return pre[x]=find(pre[x]);
}
int cnt=0;
void kruskal(){
	
	sort(arr+1,arr+1+m,cmp);
	
	for(int i=1;i<=m;i++){
		if(cnt>=n-1) break;
		ll u=arr[i].u;
		ll v=arr[i].v;
		ll w=arr[i].w;
		ll fu=find(u);
		ll fv=find(v);
		if(fu!=fv){
			vt[u].push_back({v,w});
			vt[v].push_back({u,w});
			pre[fu]=fv;
			cnt++;
			
		}
	}
}
ll dp[maxn][25];
ll st[maxn][25];
ll h[maxn];
void dfs(ll u,ll f){
	ll l=vt[u].size();
	dp[u][0]=f;
	h[u]=h[f]+1;
	for(int i=1;i<=20;i++){
		dp[u][i]=dp[dp[u][i-1]][i-1];
		st[u][i]=min(st[u][i-1],st[dp[u][i-1]][i-1]);
	}
	for(int i=0;i<l;i++){
		ll v=vt[u][i].x;
		ll p=vt[u][i].p;
		if(v==f) continue;
		st[v][0]=p;
		dfs(v,u);
	}
}
ll lca(int x,int y){
	ll a=x;
	ll b=y;
	ll ans=INF;
	if(h[a]<h[b]) swap(a,b);
	for(int i=20;i>=0;i--){
		if(h[dp[a][i]]>=h[b]){
			ans=min(ans,st[a][i]);
			a=dp[a][i];
		}
	}
	if(a==b) return ans;
	for(int i=20;i>=0;i--){
		if(dp[a][i]!=dp[b][i]){
			ans=min(ans,st[a][i]);
			ans=min(ans,st[b][i]);
			a=dp[a][i];
			b=dp[b][i];
		}
	}
	ans=min(ans,min(st[a][0],st[b][0]));
	return ans;
}
int main(){
	
	cin>>n>>m>>q; 
	for(int i=1;i<=n;i++) pre[i]=i;
	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<=m;i++) cin>>arr[i].u>>arr[i].v>>arr[i].w;
	for(int i=1;i<=q;i++) cin>>c[i];
	for(int i=1;i<q;i++){
		int fx=find(c[i]);
		int fy=find(c[i+1]);
		if(fx==fy) continue;
		pre[fx]=fy;
		vt[c[i]].push_back({c[i+1],INF});
		vt[c[i+1]].push_back({c[i],INF});
		cnt++;
	}
	kruskal();
	dfs(1,0);
	ll now=a[1];
	if(b[now]>0) money=b[now];
	else cout<<0<<endl;
	for(int i=2;i<=n;i++){
		ll to=a[i];
		//cout<<now<<" "<<to<<endl;
		ll mn=lca(a[i-1],to);
		money=min(money,mn);
		if(b[to]>0) money+=b[to];
		else{
			cout<<min(-b[to],money)<<endl;
			money-=min(-b[to],money);
		}
	}
	
	return 0;
}