POJ 3728 The merchant

题意好像不清楚：

给定一棵 $n$ 个点的树，每个点有点权 $val_i$，现在有 $q$ 个询问，每次询问给出 $u,v$，设 $u$ 到 $v$ 的路径上的点编号为 $a_1,a_2\cdots a_{len}$，求 $\max\limits_{1 \le x < y\le len}{val_{a_y}-val_{a_x}}$。

因为 $x,y$ 有顺序限制，所以不好直接做，最直观的思路应该就是对于每个询问分治，这样我们就把顺序限制干掉了，但是直接分治的复杂度是 $O(qn\log n)$ 的，直接寄。

然后我就不会做了。

发现这个题没有修改，应该是静态的东西，思考一下有什么东西像这个分治结构，看完题解后发现就是倍增，具体来讲就是我们直接维护 $up_{u,j}$ 表示从 $u$ 走到他的 $2^j-1$ 级祖先的答案，$down_{u,j}$ 表示从 $u$ 的 $2^j-1$ 级祖先走到 $u$ 的答案，$f_{u,j}$ 表示 $u$ 的 $2^j$ 级祖先是谁，$mx_{u,j}$ 表示 $u$ 到他的 $2^j-1$ 级祖先中权值最大值，$mn$ 为最小值。

在计算 $up$ 的时候是类似于 $up_{u,j}=\max(\{up_{u,j-1},up_{f_{u,j-1},j-1},mx_{f_{u,j-1},j-1}-mn_{u,j-1}\})$，这玩意就是类似于分治区间为 $u$ 到 $j$ 级祖先，然后分治成 $u$ 到 $j-1$ 级祖先和 $f_{u,j-1}$ 到 $j-1$ 级祖先两部分，然后最后的就是当前区间跨过分治中点的答案， $down$ 是同理的。

最后统计答案也是类似与分治的合并，跟上面的一样。

code:（POJ 只支持 C++98 ）

#include<cstdio>
#include<iostream>
#include<vector>
#define pb push_back
using namespace std;
const int INF=1e9+7;
const int N=5e4+7,Log=16;
int n;
int val[N];
int up[N][Log],down[N][Log],mx[N][Log],mn[N][Log],f[N][Log];
int dep[N];
vector<int>g[N];
inline void dfs(int u,int fa){
	dep[u]=dep[fa]+1;
	f[u][0]=fa,mx[u][0]=mn[u][0]=val[u];
	for(int j=1;j<Log;j++){
		f[u][j]=f[f[u][j-1]][j-1];
		mx[u][j]=max(mx[u][j-1],mx[f[u][j-1]][j-1]);
		mn[u][j]=min(mn[u][j-1],mn[f[u][j-1]][j-1]);
		up[u][j]=max(up[u][j-1],max(up[f[u][j-1]][j-1],mx[f[u][j-1]][j-1]-mn[u][j-1]));
		down[u][j]=max(down[u][j-1],max(down[f[u][j-1]][j-1],mx[u][j-1]-mn[f[u][j-1]][j-1]));
	}
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa) continue;
		dfs(v,u);
	}
}
inline int lca(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	for(int j=Log-1;j>=0;j--){
		if(dep[f[u][j]]>=dep[v]) u=f[u][j];
	}
	if(u==v) return u;
	for(int j=Log-1;j>=0;j--){
		if(f[u][j]!=f[v][j]) u=f[u][j],v=f[v][j];
	}
	return f[u][0];
}
int main(){
#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&val[i]);
	for(int i=1;i<n;i++){
		int u,v; scanf("%d%d",&u,&v);
		g[u].pb(v),g[v].pb(u);
	}
	dfs(1,0);
	int q; scanf("%d",&q);
	while(q--){
		int u,v; scanf("%d%d",&u,&v);
		int ans=0,anc=lca(u,v),MX=0,MN=INF;
		for(int j=Log-1;j>=0;j--){
			if(dep[f[u][j]]>=dep[anc]) ans=max(ans,max(up[u][j],mx[u][j]-MN)),MN=min(MN,mn[u][j]),u=f[u][j]; 
		}
		ans=max(ans,val[anc]-MN),MN=min(MN,val[anc]);
		for(int j=Log-1;j>=0;j--){
			if(dep[f[v][j]]>=dep[anc]) ans=max(ans,max(down[v][j],MX-mn[v][j])),MX=max(MX,mx[v][j]),v=f[v][j];
		}
		ans=max(ans,MX-val[anc]),MX=max(MX,val[anc]);
		printf("%d\n",max(ans,MX-MN));
	}
	return 0;
}