POJ 3728 The merchant LCA + 배 dp

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include<cmath>
#include<algorithm>
#include<stdlib.h>

using namespace std;
#define N 50010
#define Log 20
struct Edge{  
	int from, to, dis, nex;  
}edge[5*N];  
int head[N],edgenum,dis[N],fa[N][Log],dep[N];  
int dmax[N][Log];
int dmin[N][Log];
int dpup[N][Log];
int dpdown[N][Log];
int w[N];
void addedge(int u,int v,int w){  
	Edge E={u,v,w,head[u]};
	edge[edgenum] = E;
	head[u]=edgenum++;  
}
void bfs(int root){  
	queue<int> q;  
	fa[root][0]=root;dep[root]=0;dis[root]=0;  
	dmin[root][0] = dmax[root][0] = w[root];

	q.push(root);
	while(!q.empty()){  
		int u=q.front();q.pop();
		for(int i=1;i<Log;i++)if(fa[u][i-1] != -1){
			fa[u][i] = fa[fa[u][i-1]][i-1];  
			if(fa[u][i] == -1)continue;
			dmax[u][i] = max(dmax[u][i - 1], dmax[ fa[u][i-1] ][i-1]);
			dmin[u][i] = min(dmin[u][i - 1], dmin[ fa[u][i-1] ][i-1]);
			dpup[u][i] =   max(  dpup[ fa[u][i-1] ][i-1],  max(  dpup[u][i-1],dmax[fa[u][i-1]][i-1] - dmin[u][i-1]));
			dpdown[u][i] = min(dpdown[ fa[u][i-1] ][i-1],  min(dpdown[u][i-1],dmin[fa[u][i-1]][i-1] - dmax[u][i-1]));
		}
		for(int i=head[u]; ~i; i = edge[i].nex){  
			int v = edge[i].to; if(v == fa[u][0])continue;  
			dep[v]=dep[u]+1;dis[v]=dis[u]+edge[i].dis;
			fa[v][0] = u; 
			dmax[v][0] = max(w[u],w[v]);
			dmin[v][0] = min(w[u],w[v]);
			dpdown[v][0] = dpup[v][0] = w[u]-w[v];
			q.push(v);
		}  
	}
}
int lca_query(int x,int y){
	if(dep[x]<dep[y])swap(x,y);  
	for(int i=0;i<Log;i++)if((dep[x]-dep[y])&(1<<i))x=fa[x][i];  
	if(x==y)return x;  
	for(int i=Log-1;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];  
	return fa[x][0];
}
int bb[2][35];
bool flg[35];
void get_max_min(int a, int b, int &ma,int &mi,int &mca,int &mci){
	int i,j;
	memset(flg,0,sizeof flg);
	ma = mi = w[a];
	mca = mci = w[b] - w[a];
	for(i = dep[a] - dep[b],j = 0; i; i >>= 1, ++ j) if(i & 1){
		ma = max(ma,dmax[a][j]);
		mi = min(mi,dmin[a][j]);
		mca = max(mca,dpup[a][j]);
		mci = min(mci,dpdown[a][j]);
		bb[0][j] = dmax[a][j];
		bb[1][j] = dmin[a][j];
		flg[j] = 1;
		a = fa[a][j];
	}
	for(i = Log - 1; i > 0; -- i)
		for(j = i - 1; j >= 0; -- j)
			if(flg[i] && flg[j]){
				mca = max(mca,bb[0][i] - bb[1][j]);
				mci = min(mci,bb[1][i] - bb[0][j]);
			}
}
void init(){
	memset(head, -1, sizeof(head)); edgenum = 0;
	memset(dmax, 0xfc, sizeof(dmax));
	memset(dmin, 0x7f, sizeof(dmin));
	memset(dpup, 0xfc, sizeof(dpup));
	memset(dpdown, 0x7f, sizeof(dpdown));
	memset(fa, -1, sizeof(fa));
}
int n;
int main(){
	int que, u, v, i, j;
	while(~scanf("%d",&n)){
		init();
		for(i = 1; i <= n; i++)scanf("%d",&w[i]);
		for(i = 1; i <  n; i++){
			scanf("%d %d",&u,&v);
			addedge(u, v, 1); addedge(v, u, 1);
		}
		bfs(1);
		scanf("%d",&que);
		while(que--){
			scanf("%d %d",&u, &v);	int c = lca_query(u,v);
			int ma[2],mi[2],mca[2],mci[2],ans = 0;
			get_max_min(u,c,ma[0],mi[0],mca[0],mci[0]);
			get_max_min(v,c,ma[1],mi[1],mca[1],mci[1]);
			ans = max(0,max(mca[0], - mci[1]));
			ans = max(ans,ma[1] - mi[0]);
			printf("%d
",ans);
		}
	}
	return 0;
}