BZOJ3322 : [Scoi2013]摩托车交易

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

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

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

然后依次模拟即可，时间复杂度$O(mlog 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
",tmp=min(now,-(ll)b[a[i]])),now-=tmp;
  }
  return 0;
}