0x00 引入例题

P3280 [SCOI2013]摩托车交易
这道题看上去的确是一道比较明显的题，关键在于针对这种 生成树与LCA 的结合类问题的思考方式。
明确题意：

给出需要拜访的城市的顺序，每个城市可以买入或卖出给定最大值以内的数量的金条。有两种道路，一种上面限制携带的金条个数，另一种不限制。在每个城市的买入或卖出的金条尽量最大，求每次卖出的金条个数值。

这里不会详细解释为什么可以一次性拿所有、可以在路上抛弃不能拿的金条之类的贪心问题。让我们来分析一下这类题的思路。

0x10 深度思考：两个算法的特性

0x11 最小生成树 与 最大生成树

我们首先思考一下在什么情况下需要用到 生成树。
通过观察，我们不难发现， 生成树上的路径是接近于“最小代价走完所有点” 。它与欧拉路径不同点就在于一条路径可能走很多次。
而关键就在于“最小代价”与“走完所有点”之上，缺一不可。（因为只有最小代价可以考虑dp，走完所有点可以考虑欧拉路。）

总结：

1. 最小代价
2. 走完所有点
3. 舍弃不需要的边

让我们回顾一下例题。“按照拜访顺序”不就是走完所有点？这里是“金条数尽可能最大”，所以使用最大代价，因此符合两个条件，使用生成树算法。

0x12 LCA

这时，我们发现 我们需要按照拜访顺序走完整棵树，所以我们需要找到一条保证路径上的最小值最大的路径，使得整个路径受的限制最小。
很显然，我们考虑贪心的思维，要尽可找到最近的转折点，转到对应的目标点所处的路径，早拐弯少受限。

总结：

1. 贪心思想，早拐弯
2. 树形结构

这里我在第一次做这道题时想到了floyd求两个点之间最大的最小值方法，直接代替了生成树+LCA的全部功效，但是时间是我们所不可接受的。
正是因为这个错误，我们不得不考虑两者之间是否存在一种神秘的关系？

0x20 生成树 & 最近公共祖先 & 最短路

我们发现，他们两者在这道题中都符合一种类似于从起点到终点的线性递推关系。
根据floyd的特性不难发现，LCA+生成树的思想十分贴近于“两点之间的最小距离”。可是 LCA+生成树 的复杂度更优。
想到这，我们不禁有了一种更为大胆的猜想：能否用生成树+LCA替代floyd，先对着图跑一遍kruskal再用倍增法LCA？
答案很显然是，不能！
让我们考虑这样一种情况：

很显然，针对这张图，如果求c - d之间的最小距离，是20 而不是 8+18+18+15=59
因此我们发现，最短路与最小生成树之间有着本质的不同。
那刚刚究竟是什么使得我们去考虑floyd而没有发现生成树的呢？
是因为生成树的产生原因是经过所有点！
这个原因坑惨了我们啊！
因此当我们遇到生成树+LCA问题时，很容易掉到floyd的坑中！

总结一下 生成树+LCA算法的规律：

1. 经历图上每一个点
2. 考虑最大、最小解
3. 找到最大的最小值
4. 舍弃不需要用的边

0x30 解决例题

0x31 考虑问题

在本题中，只剩下最后一个问题：它明明就是图上的最大值，为什么会考虑到生成树？？？
我们可以贪心的发现，这图上面会有一些边根本使用不到，而这就是生成树的本质：舍弃不需要的边！
这道题的思路就解决了~

0x32 代码

code:

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const long long INF=1e18;
long long n,m,p;
long long tot,fa[400005],order[400005],gold[400005];
vector <long long> G[400005];
struct Edge {
	long long u,v;
	long long w;
	Edge() {}
	Edge(long long U,long long V,long long W) {
		u=U,v=V,w=W;
	}
} edge[600005];
long long findSet(long long x) {
	if(fa[x]==x) return x;
	else return fa[x]=findSet(fa[x]);
}
void kruskal() {
	long long cnt=0;
	for(long long i=1; i<=m+max(p,1ll)-1; i++) {
		long long u=edge[i].u,v=edge[i].v,w=edge[i].w;
		u=findSet(u),v=findSet(v);
		if(u!=v) {
			tot++;
			cnt++;
			gold[tot]=w;
			G[u].push_back(tot);
			G[tot].push_back(u);
			fa[u]=tot;
			G[v].push_back(tot);
			G[tot].push_back(v);
			fa[v]=tot;
		}
		if(cnt==n-1) return;
	}
}
inline bool cmp(Edge x,Edge y) {
	return x.w>y.w;
}
long long dep[400005],f[400005][20],lg[400005];
void dfs(long long u,long long fat) {
	dep[u]=dep[fat]+1;
	f[u][0]=fat;
	for(long long i=1; i<=lg[dep[u]]; i++) f[u][i]=f[f[u][i-1]][i-1];
	for(long long i=0; i<G[u].size(); i++) {
		long long v=G[u][i];
		if(v==fat) continue;
		dfs(v,u);
	}
}
long long query(long long x,long long y) {
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]>dep[y]) x=f[x][lg[dep[x]-dep[y]]-1];
	if(x==y) return gold[x];
	for(long long k=lg[dep[x]]-1; k>=0; k--) {
		if(f[x][k]!=f[y][k]) x=f[x][k],y=f[y][k];
	}
	return gold[f[x][0]];
}
int main() {
	long long root;
	scanf("%lld %lld %lld",&n,&m,&p);
	for(long long i=1; i<=n; i++) 
		fa[i]=i,lg[i]=lg[i-1]+(1<<lg[i-1]==i),scanf("%lld",&order[i]);
	for(long long i=1; i<=n; i++) 
		fa[i+n]=i+n,lg[i+n]=lg[i+n-1]+(1<<lg[i+n-1]==i+n),scanf("%lld",&gold[i]);
	for(long long i=1,u,v,w; i<=m; i++) {
		scanf("%lld %lld %lld",&u,&v,&w);
		edge[i]=Edge(u,v,w);
	}
	if(p) 
		scanf("%lld",&root);
	for(long long i=1,q; i<p; i++) {
		scanf("%lld",&q);
		edge[m+i]=Edge(root,q,INF);
	}
	tot=n;
	sort(edge+1,edge+m+max(p,1ll),cmp);
	kruskal();

	dfs(tot,0);

	long long now=gold[order[1]];
	if(now<=0) puts("0"),now=0;
	for(long long i=1; i<n; i++) {
		long long x=order[i],y=order[i+1];
		long long re=query(x,y);
		now=min(now,re);
		if(gold[y]>0) now+=gold[y];
		else {
			if(now+gold[y]>=0) 
				printf("%lld\n",-gold[y]),now+=gold[y];
			else 
				printf("%lld\n",now),now=0;
		}
	}
	return 0;
}