Description
小B正在树上漫步，突然接到了小S的电话，要他去点y买一些礼物，然而他现在正处于x点，然而他身上并没有钱(其实钱无限多)。这个时候，小B遇到了小L，小L告诉了他一个绝妙的方法，因为树上的每个点都有dalao的存在，而这些dalao当中总有购买或出售（出售和购买价格相同）bsoj权限账号的人，而且因为各点dalao数量不同，价格也不同，这样的交易能使他赚上一笔。小S没有告诉他礼物的价钱，他只能赚尽量多的钱。由于小S在小B的身上装了追踪，所以他只能走x到y的最短路，而且时间不足，因此这样的交易只能发生一次。
小B这样的大神犇显然已经知道求解方法了，但他为了不被小S发现，让你来帮他解决这个问题。
小B这样的大神犇显然已经知道求解方法了，但他为了不被小S发现，让你来帮他解决这个问题。
Input
输入第一行是一个整数 n，表示树上的点数。
接下来n个正整数，表示每个点上权限号的价格。
接下来n-1行，每行两个整数x，y，表示第x点和第y点有一条边。
接下来一个整数m，表示下来有m个询问。
接下来有m行，每行两个整数x和y，表示小B从第x点出发要到第y点。
接下来n个正整数，表示每个点上权限号的价格。
接下来n-1行，每行两个整数x，y，表示第x点和第y点有一条边。
接下来一个整数m，表示下来有m个询问。
接下来有m行，每行两个整数x和y，表示小B从第x点出发要到第y点。
Output
输出包括m行。
每行对应一个询问，一个整数，表示小B最多能赚到多少钱。
每行对应一个询问，一个整数，表示小B最多能赚到多少钱。
Sample Input
10
3 4 1 2 7 6 1 5 3 9
1 2
1 9
3 1
9 7
5 9
6 9
8 7
4 7
10 7
3
5 6
8 10
2 4
Sample Output
3
8
1
Hint
【规模与约定】
对于前40%数据 n<=1000， m<=1000
对于100%数据 n<=250000 ，m<=10000，所有权限号的价格在int范围之内。
对于前40%数据 n<=1000， m<=1000
对于100%数据 n<=250000 ，m<=10000，所有权限号的价格在int范围之内。
题解：
40分做法:
这个范围显然暴力能过啊
先将两点跳到同一高度，再同时往上跳
以起点为例，跳的时候不断维护最小值，并用当前点价减去最小值维护答案
终点往上跳就相反
到了最近公共祖先再拿maxn-minn维护最大答案
时间O(nm)
100分做法:
讲讲倍增的方法
两边的最大最小值的维护就不用讲了吧
再记录两个值up[x][i] down[x][i]从x点往上或往下走2^i中交易能赚到的最多钱
这样向上跳的时候，不仅要用up down更新答案
对于左边，要时刻用现在的最大值-历史的最小值更新答案
对于右边，要时刻用历史的最大值-现在的最小值更新答案
最后同理也要maxn-minn更新
时间O(m log2n)
code：
1 #include<iostream> 2 #include<cstdio> 3 #define N 100005 4 using namespace std; 5 struct node { 6 int u,v; 7 } e[N]; 8 int first[N],nxt[N],cnt; 9 void add(int u,int v) { 10 e[++cnt].u=u; 11 e[cnt].v=v; 12 nxt[cnt]=first[u]; 13 first[u]=cnt; 14 } 15 int fa[N][30],mi[N][30],mx[N][30],zhengmx[N][30],fanmx[N][30],dep[N],val[N]; 16 void dfs(int x,int father) { 17 for(int i=first[x]; i; i=nxt[i]) { 18 int v=e[i].v; 19 if(v==father)continue; 20 fa[v][0]=x; 21 mi[v][0]=min(val[x],val[v]); 22 mx[v][0]=max(val[x],val[v]); 23 zhengmx[v][0]=max(0,val[v]-val[x]); 24 fanmx[v][0]=max(0,val[x]-val[v]); 25 dep[v]=dep[x]+1; 26 dfs(v,x); 27 } 28 } 29 int lca(int x,int y) { 30 if(dep[y]>dep[x])swap(x,y); 31 for(int i=19; i>=0; i--) { 32 if(dep[fa[x][i]]>=dep[y]) 33 x=fa[x][i]; 34 if(x==y)return x; 35 } 36 for(int i=19; i>=0; i--) { 37 if(fa[x][i]==fa[y][i])continue; 38 x=fa[x][i],y=fa[y][i]; 39 } 40 return fa[x][0]; 41 } 42 int read(){ 43 int x=0,f=1; 44 char c=getchar(); 45 while(!isdigit(c)){ 46 if(c=='-')f=-1; 47 c=getchar(); 48 } 49 while(isdigit(c)){ 50 x=(x<<3)+(x<<1)+c-'0'; 51 c=getchar(); 52 } 53 return x*f; 54 } 55 int main() { 56 freopen("gift.in","r",stdin); 57 freopen("gift.out","w",stdout); 58 int n; 59 n=read(); 60 for(int i=1; i<=n; i++)val[i]=read(); 61 for(int i=1; i<n; i++) { 62 int u,v; 63 u=read(); 64 v=read(); 65 add(u,v); 66 add(v,u); 67 } 68 fa[1][0]=1; 69 zhengmx[1][0]=fanmx[1][0]=0; 70 mx[1][0]=mi[1][0]=val[1]; 71 dfs(1,1); 72 //for(int i=1;i<=n;i++)cout<<" father->"<<fa[i][0]; 73 for(int i=1; i<=20; i++) { 74 for(int j=1; j<=n; j++) { 75 // if(dep[j]-(i<<i)<0)break; 76 fa[j][i]=fa[fa[j][i-1]][i-1]; 77 mx[j][i]=max(mx[j][i-1],mx[fa[j][i-1]][i-1]); 78 mi[j][i]=min(mi[j][i-1],mi[fa[j][i-1]][i-1]); 79 zhengmx[j][i]=max(zhengmx[j][i-1],max(zhengmx[fa[j][i-1]][i-1],mx[j][i-1]-mi[fa[j][i-1]][i-1])); 80 fanmx[j][i]=max(fanmx[j][i-1],max(fanmx[fa[j][i-1]][i-1],mx[fa[j][i-1]][i-1]-mi[j][i-1])); 81 } 82 } 83 // for(int i=1; i<=n; i++)cout<<"now->"<<i<<" zhengmx[i]->"<<zhengmx[i][1]<<" fanmx[i]->"<<fanmx[i][1]<<" max->"<<mx[i][1]<<" min->"<<mi[i][1]<<" fa->"<<fa[i][1]<<' '; 84 // cout<<zhengmx[10][1]; 85 int Q; 86 Q=read(); 87 while(Q--) { 88 int u,v; 89 u=read(); 90 v=read(); 91 int all=lca(u,v); 92 int max0=0,ans=0,min0=0x3f3f3f3f; 93 for(int i=19; i>=0; i--) { 94 if(dep[fa[u][i]]>=dep[all]) { 95 ans=max(fanmx[u][i],ans); 96 ans=max(ans,mx[u][i]-min0); 97 min0=min(min0,mi[u][i]); 98 u=fa[u][i]; 99 } 100 if(dep[fa[v][i]]>=dep[all]) { 101 ans=max(zhengmx[v][i],ans); 102 ans=max(ans,max0-mi[v][i]); 103 max0=max(max0,mx[v][i]); 104 v=fa[v][i]; 105 } 106 } 107 cout<<max(ans,max0-min0)<<' '; 108 } 109 return 0; 110 }
over