poj 3728 The merchant

题意：

求树上x->y的路径最大差值，且大的权在小的权之后。

题解：

挺好的一道经典陈题。

首先好像有种差分+树剖的做法，但太恶心。

扫一眼题解，发现要维护一大堆东西，于是YY了下，好像可以。

大概是这样的：

struct trnode{
    int dis,fa[20],max[20],min[20],up[20],down[20];
}tr[50010];
           

分别是，x的 2i 的祖先，这一段上最大值，最小值，从x-> 2ifa 的答案，从 2ifa ->x的答案。

写考虑暴力做法，枚举路径，用当前值-已有的最小值更新答案。

那么现在可以倍增求这些东西，分两段，x->lca与lca->y。

我也不知道在口胡什么，具体代码

还有种离线的做法，然而我并不会，丢链接：ozy

总结：

想做这种题最好别想太多，变一变就好。

有时就差一点灵感。

剩下99%都是码代码。

但灵感更重要。

code：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
const int inf=(<<);
struct node{
    int y,next;
}a[];int len=,last[];
int n,w[];
struct trnode{
    int dis,fa[],max[],min[],up[],down[];
}tr[];
void ins(int x,int y)
{
    a[++len].y=y;
    a[len].next=last[x];last[x]=len;
}
void cmax(int &x,int y){x=max(x,y);}
void cmin(int &x,int y){x=min(x,y);}
void dfs(int x,int fa)
{
    tr[x].dis=tr[fa].dis+;
    tr[x].fa[]=fa;
    if(fa!=) cmax(tr[x].up[],w[fa]-w[x]);
    if(fa!=) cmax(tr[x].down[],w[x]-w[fa]);
    tr[x].max[]=tr[x].min[]=w[x];
    if(fa!=) cmax(tr[x].max[],w[fa]);
    if(fa!=) cmin(tr[x].min[],w[fa]);
    for(int i=;(<<i)<=tr[x].dis;i++)
    {
        int y=tr[x].fa[i-];
        tr[x].fa[i]=tr[y].fa[i-];
        cmax(tr[x].up[i],max(tr[x].up[i-],tr[y].up[i-]));
        cmax(tr[x].up[i],tr[y].max[i-]-tr[x].min[i-]);
        cmax(tr[x].down[i],max(tr[x].down[i-],tr[y].down[i-]));
        cmax(tr[x].down[i],tr[x].max[i-]-tr[y].min[i-]);
        tr[x].max[i]=max(tr[x].max[i-],tr[y].max[i-]);
        tr[x].min[i]=min(tr[x].min[i-],tr[y].min[i-]);
    }
    for(int i=last[x];i;i=a[i].next)
    {
        int y=a[i].y;
        if(y!=fa) dfs(y,x);
    }
}
int getlca(int x,int y)
{
    if(tr[x].dis<tr[y].dis) swap(x,y);
    for(int i=;i>=;i--)
        if((<<i)<=tr[x].dis-tr[y].dis) x=tr[x].fa[i];
    if(x==y) return x;
    for(int i=;i>=;i--)
        if((<<i)<=tr[x].dis&&tr[x].fa[i]!=tr[y].fa[i]) x=tr[x].fa[i],y=tr[y].fa[i];
    return tr[x].fa[];
}
int solve(int x,int y)
{
    int lca=getlca(x,y);
    int ans=;
    int mx=w[y],mn=w[x];
    for(int i=;i>=;i--)
        if((<<i)<=tr[x].dis-tr[lca].dis)
        {
            cmax(ans,tr[x].up[i]);
            cmax(ans,tr[x].max[i]-mn);
            cmin(mn,tr[x].min[i]);
            x=tr[x].fa[i];
        }
    for(int i=;i>=;i--)
        if((<<i)<=tr[y].dis-tr[lca].dis)
        {
            cmax(ans,tr[y].down[i]);
            cmax(ans,mx-tr[y].min[i]);
            cmax(mx,tr[y].max[i]);
            y=tr[y].fa[i];
        }
    cmax(ans,mx-mn);
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=;i<=n;i++) scanf("%d",&w[i]);
    for(int i=;i<n;i++)
    {
        int x,y;scanf("%d %d",&x,&y);
        ins(x,y);ins(y,x);
    }
    tr[].dis=-;dfs(,);
    int q;scanf("%d",&q);
    while(q--)
    {
        int x,y;scanf("%d %d",&x,&y);
        printf("%d\n",solve(x,y));
    }
}