BZOJ3322 : [Scoi2013]摩托车交易

求出最大生成树，则两点间的最大容量为树上两点间的边权的最小值。

设$lim[i]$表示第$i$个订单的城市允许携带的黄金上限，则

$lim[i]=\min(lim[i+1],a[i]和a[i+1]点间最大容量)+\max(0,-b[a[i]])$

然后依次模拟即可，时间复杂度$O(m\log n)$。

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=100010,K=16;

const ll inf=1LL<<60;

int n,m,q,i,j,a[N],b[N],c[N],fa[N],g[N],v[N<<1],nxt[N<<1],ed;

int d[N],f[K+1][N];

ll w[N<<1],fm[K+1][N],now,tmp,lim[N];

struct E{int x,y;ll z;}e[300010];

inline bool cmp(const E&a,const E&b){return a.z>b.z;}

int F(int x){return fa[x]==x?x:fa[x]=F(fa[x]);}

inline void add(int x,int y,ll z){

  v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;

  v[++ed]=x;w[ed]=z;nxt[ed]=g[y];g[y]=ed;

}

void dfs(int x,int y,ll z){

  d[x]=d[f[0][x]=y]+1,fm[0][x]=z;

  for(int i=1;i<=K;i++)f[i][x]=f[i-1][f[i-1][x]],fm[i][x]=min(fm[i-1][x],fm[i-1][f[i-1][x]]);

  for(int i=g[x];i;i=nxt[i])if(v[i]!=y)dfs(v[i],x,w[i]);

}

inline ll ask(int x,int y){

  ll t=inf;

  if(x==y)return t;

  if(d[x]<d[y])swap(x,y);

  for(int i=K;~i;i--)if(d[f[i][x]]>=d[y])t=min(t,fm[i][x]),x=f[i][x];

  if(x==y)return t;

  for(int i=K;~i;i--)if(f[i][x]!=f[i][y])t=min(t,min(fm[i][x],fm[i][y])),x=f[i][x],y=f[i][y];

  return min(t,min(fm[0][x],fm[0][y]));

}

inline void read(int&a){

  char c;bool f=0;a=0;

  while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));

  if(c!='-')a=c-'0';else f=1;

  while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';

  if(f)a=-a;

}

int main(){

  read(n),read(m),read(q);

  for(i=1;i<=n;i++)read(a[i]);

  for(i=1;i<=n;i++)read(b[i]);

  for(i=1;i<=m;i++)read(e[i].x),read(e[i].y),read(j),e[i].z=j;

  for(i=1;i<=q;i++)read(c[i]);

  for(i=1;i<q;i++)e[++m].x=c[i],e[m].y=c[q],e[m].z=inf;

  for(i=1;i<=n;i++)fa[i]=i;

  sort(e+1,e+m+1,cmp);

  for(i=1;i<=m;i++)if(F(e[i].x)!=F(e[i].y))fa[fa[e[i].x]]=fa[e[i].y],add(e[i].x,e[i].y,e[i].z);

  dfs(1,0,0);

  lim[n]=max(0,-b[a[n]]);

  for(lim[n]=max(0,-b[a[n]]),i=n-1;i;i--)lim[i]=min(lim[i+1],ask(a[i],a[i+1]))+max(0,-b[a[i]]);

  for(i=1;i<=n;i++){

    if(b[a[i]]>0)now=min(1LL*(now+b[a[i]]),lim[i]);

    else printf("%lld\n",tmp=min(now,-(ll)b[a[i]])),now-=tmp;

  }

  return 0;

}