【[SCOI2013]機車交易 】

倍增什麼的最慢了，常數太大了

我們可以上樹剖啊

但是如果用樹剖來查詢樹上兩點之間的最小邊權的話，可能隻能在上一棵線段樹？

那也太\(naive\)了，盡管倍增常數大，但是還是比兩個\(log\)快的

那幹脆重構樹算了

我們直接建出\(kruskal\)重構樹，之後我們可以在重構樹上直接用樹剖來查詢\(lca\)，\(lca\)的點權就是最小邊的邊權

這就是我最優解的原因了

之後發現自己的思路非常清奇，那就幹脆再寫一下思路吧

可能是我太傻了，并沒有發現可以直接貪心，是以搞出來一種非常難寫的方法

我們定義一個\(Maxn\)數組，\(Maxn[i]\)表示\(i\)次交易後最多可以攜帶多少枚金子

顯然\(Maxn[n]=0\)，\(n\)次交易後我們不能再有金子了

之後我們倒着推出\(Maxn\)數組

首先\(Maxn[i]\)應該等于\(i\)次交易和\(i+1\)次交易之間兩點的最小邊權

如果\(a[i+1]<0\)，我們可以通過賣出消耗掉一些,那就說明我們可以多往後傳遞一些，于是就有\(Maxn[i]-|a[i+1]|<=Maxn[i+1]\)

也就是\(Maxn[i]<=Maxn[i]-a[i+1]\)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#define re register
#define maxn 100005
#define INF 9999999999
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
struct E
{
	int v,nxt;
}e[maxn<<2];
struct g
{
	int x,y;
	LL z;
}G[maxn<<1];
int fa[maxn<<1];
int sum[maxn<<1],Fa[maxn<<1],top[maxn<<1],deep[maxn<<1],son[maxn<<1],head[maxn<<1];
int n,m,q,num;
LL Maxn[maxn];
int c[maxn<<1];
LL a[maxn],b[maxn];
LL val[maxn<<2];
inline LL read()
{
	char c=getchar();
	LL x=0,r=1;
	while(c<'0'||c>'9') {if(c=='-') r=-1;c=getchar();}
	while(c>='0'&&c<='9')
		x=(x<<3)+(x<<1)+c-48,c=getchar();
	return x*r;
}
inline int find(int x)
{
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
inline void add_edge(int x,int y)
{
	e[++num].v=y;
	e[num].nxt=head[x];
	head[x]=num;
}
void dfs1(int x)
{
	sum[x]=1;
	int maxx=-1;
	for(re int i=head[x];i;i=e[i].nxt)
	if(!deep[e[i].v])
	{
		deep[e[i].v]=deep[x]+1;
		Fa[e[i].v]=x;
		dfs1(e[i].v);
		sum[x]+=sum[e[i].v];
		if(sum[e[i].v]>maxx) maxx=sum[e[i].v],son[x]=e[i].v;
	}
}
void dfs2(int x,int topf)
{
	top[x]=topf;
	if(!son[x]) return;
	dfs2(son[x],topf);
	for(re int i=head[x];i;i=e[i].nxt)
	if(deep[e[i].v]>deep[x]&&son[x]!=e[i].v) dfs2(e[i].v,e[i].v);
}
inline int LCA(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(deep[top[x]]<deep[top[y]]) std::swap(x,y);
		x=Fa[top[x]];
	}
	if(deep[x]<deep[y]) return x;
	return y;
}
inline int cmp(g a,g b)
{
	return a.z>b.z;
}
signed main()
{
	n=read(),m=read(),q=read();
	for(re int i=1;i<=n;i++) b[i]=read();
	for(re int i=1;i<=n;i++) a[i]=read();
	for(re int i=1;i<=m;i++)
		G[i].x=read(),G[i].y=read(),G[i].z=read();
	for(re int i=1;i<=n*2;i++) c[i]=i;
	if(q>=1)
	{
		int pre=read(),X;
		for(re int i=1;i<q;i++)
		{
			X=read();
			c[X]=pre;
		}
	}
	std::sort(G+1,G+m+1,cmp);
	for(re int i=1;i<=n*2;i++)
	if(c[i]==i) fa[i]=i;
	int cnt=n;
	for(re int i=1;i<=m;i++)
	{
		int xx=find(c[G[i].x]);
		int yy=find(c[G[i].y]);
		if(xx==yy) continue;
		add_edge(++cnt,xx),add_edge(cnt,yy);
		add_edge(xx,cnt),add_edge(yy,cnt);
		val[cnt]=G[i].z;
		fa[xx]=cnt,fa[yy]=cnt;
	}
	deep[cnt]=1;
	dfs1(cnt);
	dfs2(cnt,cnt);
	Maxn[n]=0;
	for(re int i=n-1;i;i--)
	{
		int lca=LCA(c[b[i]],c[b[i+1]]);
		Maxn[i]=val[lca];
		if(lca==c[b[i]]) Maxn[i]=INF;
		if(a[b[i+1]]<0)
			Maxn[i]=min(Maxn[i+1]-a[b[i+1]],Maxn[i]);
		else
			Maxn[i]=min(Maxn[i],Maxn[i+1]);
	}
	LL now=0;
	for(re int i=1;i<=n;i++)
	{
		if(a[b[i]]>0) now=min(Maxn[i],a[b[i]]+now);
		else 
		{
			printf("%lld\n",min(now,-a[b[i]]));
			now+=a[b[i]];
			now=max(now,0);
		}
	}
	return 0;
}