传送门
题目大意：给定一棵树，点有点权，若干询问，每次询问从u到v的路径（v到u不算）中，选择一个点的点权和之后的一个点的点权，使得之后这个点的点权减去之前这个点的点去之差最大。
题解：首先肯定要求LCA。
看网上说什么并查集之类的好麻烦啊不明觉厉。
我的做法非常简单，考虑求LCA时候依次切出来的不超过O(lgn)个区间，答案要么完全在某一个区间中，要么画一条线把这些区间分为两部分，
从前面选择最小值，从后面选择最大值。
所以我们要求每一段区间的答案、最小值、最大值。这个显然在求倍增数组的时候顺便求一下即可。
复杂度O((n+q)lgn)。
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<climits> #define INF (INT_MAX/2-10) #define MAXM 100010 #define MAXN 50010 #define MAXL 20 #define debug(x) cerr<<#x<<"="<<x #define sp <<" " #define ln <<endl using namespace std; struct edges{ int to,pre; }e[MAXM]; int h[MAXN],etop,dep[MAXN],w[MAXN]; inline int add_edge(int u,int v) { etop++; e[etop].to=v; e[etop].pre=h[u]; h[u]=etop; return 0; } int up[MAXN][MAXL],minn[MAXN][MAXL],maxn[MAXN][MAXL],ans[MAXN][MAXL],ans2[MAXN][MAXL]; inline int dfs(int x,int fa) { up[x][0]=fa,maxn[x][0]=max(w[x],w[fa]),dep[x]=dep[fa]+1; minn[x][0]=min(w[x],w[fa]),ans[x][0]=max(0,w[fa]-w[x]),ans2[x][0]=max(0,w[x]-w[fa]); for(int i=1;i<MAXL;i++) up[x][i]=up[up[x][i-1]][i-1], maxn[x][i]=max(maxn[x][i-1],maxn[up[x][i-1]][i-1]), minn[x][i]=min(minn[x][i-1],minn[up[x][i-1]][i-1]), ans[x][i]=max(ans[x][i-1],ans[up[x][i-1]][i-1]), ans[x][i]=max(ans[x][i],maxn[up[x][i-1]][i-1]-minn[x][i-1]), ans2[x][i]=max(ans2[x][i-1],ans2[up[x][i-1]][i-1]), ans2[x][i]=max(ans2[x][i],maxn[x][i-1]-minn[up[x][i-1]][i-1]); for(int i=h[x];i;i=e[i].pre) if(e[i].to^fa) dfs(e[i].to,x); return 0; } inline int getLCA(int u,int v) { if(dep[u]<dep[v]) swap(u,v); for(int i=MAXL-1;i>=0;i--) if(dep[up[u][i]]>=dep[v]) u=up[u][i]; if(u==v) return u; for(int i=MAXL-1;i>=0;i--) if(up[u][i]!=up[v][i]) u=up[u][i],v=up[v][i]; return up[u][0]; } int maxa[MAXN],maxb[MAXN],mina[MAXN],minb[MAXN]; inline int solve(int u,int v) { int n1=0,n2=0,pans=0; int x=getLCA(u,v); maxa[0]=0,mina[0]=INF; maxb[0]=0,minb[0]=INF; for(int i=MAXL-1;i>=0;i--) if(dep[up[u][i]]>=dep[x]) { n1++;maxa[n1]=maxn[u][i]; mina[n1]=min(mina[n1-1],minn[u][i]); pans=max(pans,ans[u][i]);u=up[u][i]; } // debug(n1)ln; // for(int i=1;i<=n1;i++) debug(maxa[i])sp;cout ln; // for(int i=1;i<=n1;i++) debug(mina[i])sp;cout ln; for(int i=1;i<=(n1>>1);i++) swap(maxa[i],maxa[n1-i+1]); for(int i=MAXL-1;i>=0;i--) if(dep[up[v][i]]>=dep[x]) { n2++;maxb[n2]=max(maxb[n2-1],maxn[v][i]); minb[n2]=minn[v][i]; pans=max(pans,ans2[v][i]);v=up[v][i]; } // debug(n2)ln; // for(int i=1;i<=n2;i++) debug(maxb[i])sp;cout ln; // for(int i=1;i<=n2;i++) debug(minb[i])sp;cout ln; for(int i=1;i<=(n2>>1);i++) swap(minb[i],minb[n2-i+1]); for(int i=1;i<=n2;i++) mina[n1+i]=min(mina[n1+i-1],minb[i]); for(int i=1;i<=n1;i++) maxb[n2+i]=max(maxb[n2+i-1],maxa[i]); int n=n1+n2; for(int i=1;i<=n;i++) pans=max(pans,maxb[n-i]-mina[i]); // for(int i=1;i<=n;i++) debug(mina[i])sp;cout ln; // for(int i=1;i<=n;i++) debug(maxb[i])sp;cout ln; return pans; } int main() { int n; while(scanf("%d",&n)!=EOF&&n) { for(int i=1;i<=n;i++) scanf("%d",&w[i]); memset(h,0,sizeof(h)),etop=0; for(int i=1;i<n;i++) { int u,v;scanf("%d%d",&u,&v); add_edge(u,v),add_edge(v,u); } int rt=1,q;dfs(rt,0);scanf("%d",&q); /* while(1) { int u,k;scanf("%d%d",&u,&k);debug(w[u])ln,debug(up[u][k])ln; debug(minn[u][k])ln,debug(maxn[u][k])ln, debug(ans[u][k])ln,debug(ans2[u][k])ln; }*/ while(q--) { int u,v;scanf("%d%d",&u,&v); printf("%d\n",solve(u,v)); } } return 0; }