POJ 3728 The merchant（倍增LCA）

题目链接

Description

There are N cities in a country, and there is one and only one simple path between each pair of cities. A merchant has chosen some paths and wants to earn as much money as possible in each path. When he move along a path, he can choose one city to buy some goods and sell them in a city after it. The goods in all cities are the same but the prices are different. Now your task is to calculate the maximum possible profit on each path.

Input

The first line contains N, the number of cities.

Each of the next N lines contains wi the goods' price in each city.

Each of the next N-1 lines contains labels of two cities, describing a road between the two cities.

The next line contains Q, the number of paths.

Each of the next Q lines contains labels of two cities, describing a path. The cities are numbered from 1 to N.

1 ≤ N, wi, Q ≤ 50000 

Output

The output contains Q lines, each contains the maximum profit of the corresponding path. If no positive profit can be earned, output 0 instead.

Sample Input

4
1 
5 
3 
2
1 3
3 2
3 4
9
1 2
1 3
1 4
2 3
2 1
2 4
3 1
3 2
3 4      

Sample Output

4
2
2
0
0
0
0
2
0      

题意：现在有一棵树，每个节点都有权值，现在给出树中的两个节点（一个为起点，一个为终点），现在要求从起点开始开始往终点走，路经一些节点，现在要求找任意两个节点的最大差值（注意：差值一定先遍历到小的，后遍历到大的，例如：1 2 3 4 5。它们的权值为3,7,6,7,2。最大差值为（7-3）而不是（7-2）因为从1到5的路上7在2前面）。

题解：首先我们应该清楚树的任意两个节点之间的路径如果不走重复的，就只有一条。所以我们需要找到两个节点LCA，这个用倍增直接找，但是怎么找题中要求的数据，就有点难了。

首先我们声明一个Max[maxn][33],Min[maxn][33]保存节点之间的最大值与最小值。

再声明两个数组up[maxn][33]保存一个节点到它上面节点的最大差值，down[maxn][33]保存一个节点到它下面节点的最大差值。

然后就好想了，若需要找(u,v)之间的最大差值，设fa为u，v的LCA，只需要找u到fa向上的最大差值，我们保存在up数组中；然后找v到fa的最大差值，我们保存在down数组数组中。要是最大差值在这两个数组中，这直接就是答案。

但是若最小值在u-fa中的节点中,最大值在fa-v中的节点中，我们就需要找两段路径的最大值和最小值了，最大值与最小值我们保存在Max和Min数组中，这个直接找就行了。

这些东西都找到了，后面就直接输出答案就行了，若还不懂看下面代码吧。

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
//#include<unordered_map>
//#include<unordered_set>
const int maxn=5e4+5;
const int mod=20190414;
const int inf=1e9;
const long long onf=1e18;
#define me(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x&(-x)
#define mid l+(r-l)/2
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define PI 3.14159265358979323846
int dir[4][2]= {0,-1,-1,0,0,1,1,0};
int dx[]= {-2,-2,-1,-1,1,1,2,2};
int dy[]= {-1,1,-2,2,-2,2,-1,1};
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int val[maxn],head[maxn<<1],cnt;
int Max[maxn][33],Min[maxn][33],up[maxn][33],down[maxn][33],father[maxn][33];
int depth[maxn];
int n;
struct node{
    int v,next;
}tree[maxn<<1];
void init() {
    cnt=0;
    me(head,-1);
}
void add_edge(int u,int v){
    tree[cnt].v=v;
    tree[cnt].next=head[u];
    head[u]=cnt++;
}
void BFS(int root){///处理所有我们需要的信息
    queue<int>q;
    father[root][0]=root;
    depth[root]=0;
    q.push(root);
    while(!q.empty()){
        int fa=q.front();
        q.pop();
        for(int i=1;(1<<i)<=n;i++){
            father[fa][i]=father[father[fa][i-1]][i-1];///跟新父节点
            Max[fa][i]=max(Max[fa][i-1],Max[father[fa][i-1]][i-1]);///更新区间最大值
            Min[fa][i]=min(Min[fa][i-1],Min[father[fa][i-1]][i-1]);///更新区间最小值
            down[fa][i]=max(max(0,Max[fa][i-1]-Min[father[fa][i-1]][i-1]),max(down[fa][i-1],down[father[fa][i-1]][i-1]));///跟新往下的最大差值
            up[fa][i]=max(max(0,Max[father[fa][i-1]][i-1]-Min[fa][i-1]),max(up[father[fa][i-1]][i-1],up[fa][i-1]));///跟新往上的最大差值
        }
        for(int i=head[fa];i!=-1;i=tree[i].next){
            int v=tree[i].v;
            if(v==father[fa][0])
                continue ;
            father[v][0]=fa;
            depth[v]=depth[fa]+1;
            Max[v][0]=max(val[fa],val[v]);
            Min[v][0]=min(val[fa],val[v]);
            down[v][0]=max(0,val[v]-val[fa]);
            up[v][0]=max(0,val[fa]-val[v]);
            q.push(v);
        }
    }
}
int LCA(int u,int v){///找两节点最近父节点
    if(depth[u]>depth[v])
        swap(u,v);
    for(int ret=depth[v]-depth[u],i=0;ret;ret>>=1,i++){
        if(ret&1)
            v=father[v][i];
    }
    if(u==v)
        return v;
    for(int i=log2(n);i>=0;i--){
        if(father[u][i]==father[v][i])
            continue ;
        v=father[v][i];
        u=father[u][i];
    }
    return father[u][0];
}
int get_up(int u,int ret,int &min_val){///找向上最大差值
    int ans=0;
    min_val=inf;
    for(int i=log2(n);i>=0;i--){
        if(ret&(1<<i)){
            ans=max(ans,Max[u][i]-min_val);///跟新区间最大差值，注意这一句不能和下面维护维护最小值的语句换位置，因为要保证最小值在最大值前面出现
            min_val=min(min_val,Min[u][i]);///记录u-fa中节点的最小值
            ans=max(ans,up[u][i]);///维护向上最大差值
            u=father[u][i];
        }
    }
    return ans;
}
int get_down(int v,int ret,int &max_val){///跟get_up函数用法相同
    int ans=0;
    max_val=0;
    for(int i=log2(n);i>=0;i--){
        if(ret&(1<<i)){
            ans=max(ans,max_val-Min[v][i]);
            max_val=max(max_val,Max[v][i]);///记录u-fa中节点的最大值
            ans=max(ans,down[v][i]);
            v=father[v][i];
        }
    }
    return ans;
}
int main()
{
    init();
    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);
        add_edge(u,v),add_edge(v,u);
    }
    BFS(1);
    int q;
    scanf("%d",&q);
    while(q--){
        int u,v;
        scanf("%d%d",&u,&v);
        int t_father=LCA(u,v);
        int Max,Min;
        int temp2=get_up(u,depth[u]-depth[t_father],Min);///找u-fa路径中的最大差值（向上最大差值）
        int temp1=get_down(v,depth[v]-depth[t_father],Max);///找fa-v的最大差值（向下最大差值）
        int ans=max(max(temp1,temp2),max(0,Max-Min));///输出u-fa,fa-v和u-fa中的最小值与fa-v中的最大值之差，三者中的最大值
        printf("%d\n",ans);
    }
    return 0;
}