poj3728The merchant树剖+线段树

如果直接在一条直线上，那么就建线段树

考虑每一个区间维护最小值和最大值和答案，就符合了合并的条件，一个log轻松做

那么在树上只要套一个树剖就搞定了，多一个log也不是问题

注意考虑在树上的话每一条链都有可能是正着被用和反着被用，所以存两个答案

所以维护信息只需要一个merge和一个reverse

代码如下：

 #include <cstdio>

 #include <iostream>

 #define mid (l+r>>1)

 using namespace std;

 struct node

 {

     int ma,mi,ans,rev_ans;

     node()

     {

         ma=;mi=;ans=;rev_ans=;

     }

     node(int a,int b,int c,int d)

     {

         ma=a;mi=b;ans=c;rev_ans=d;

     }

     void rever()

     {

         swap(ans,rev_ans);

     }

 } tr[];

 int N,TIME,n,m,p,q;

 int to[],nex[],fir[],w[],pos[],loc[];

 int fa[],size[],dep[],top[];

 node merge(node a,node b)

 {

     return node(max(a.ma,b.ma),min(a.mi,b.mi),max(b.ma-a.mi,max(a.ans,b.ans)),max(a.ma-b.mi,max(a.rev_ans,b.rev_ans)));

 }

 void add(int p,int q)

 {

     to[++N]=q;nex[N]=fir[p];fir[p]=N;

     to[++N]=p;nex[N]=fir[q];fir[q]=N;

 }

 int build(int now,int fat)

 {

     fa[now]=fat;size[now]=;dep[now]=dep[fat]+;

     for(int i=fir[now];i;i=nex[i])

     if(to[i]!=fat)

         size[now]+=build(to[i],now);

     return size[now];

 }

 void pou(int now,int tp)

 {

     top[now]=tp;loc[++TIME]=now;

     pos[now]=TIME;

     int best=;

     for(int i=fir[now];i;i=nex[i])

     if(to[i]!=fa[now])

         best=best?((size[best]<size[to[i]])?to[i]:best):to[i];

     if(best)

     pou(best,tp);

     for(int i=fir[now];i;i=nex[i])

     if(to[i]!=fa[now] && to[i]!=best)

         pou(to[i],to[i]);

 }

 void work(int now,int l,int r)

 {

     if(l==r)

     {

         tr[now]=node(w[loc[l]],w[loc[l]],,);

         return;

     }

     work(now<<,l,mid);

     work(now<<|,mid+,r);

     tr[now]=merge(tr[now<<],tr[now<<|]);

 }

 node que(int now,int l,int r,int x,int y)

 {

     if(l==x && r==y)

         return tr[now];

     node ret=node();

     if(x<=mid)

         ret=que(now<<,l,mid,x,min(y,mid));

     if(y>mid)

         ret=merge(ret,que(now<<|,mid+,r,max(mid+,x),y));

     return ret;

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

         scanf("%d",&w[i]);

     for(int i=;i<n;i++)

         scanf("%d%d",&p,&q),add(p,q);

     build(,);

     pou(,);

     work(,,n);

     scanf("%d",&m);

     for(int i=;i<=m;i++)

     {

         scanf("%d%d",&p,&q);

         node P=node(),Q=node();

         while(top[p]!=top[q])

         {

             if(dep[top[p]]<dep[top[q]])

             {//work on q

                 Q=merge(que(,,n,pos[top[q]],pos[q]),Q);

                 q=fa[top[q]];

             }

             else

             {//work on p

                 node now=que(,,n,pos[top[p]],pos[p]);

                 now.rever();

                 P=merge(P,now);

                 p=fa[top[p]];

             }

         }

         if(dep[p]<dep[q])

             P=merge(P,que(,,n,pos[p],pos[q]));

         else

         {

             node now=que(,,n,pos[q],pos[p]);

             now.rever();

             P=merge(P,now);

         }

         P=merge(P,Q);

         printf("%d\n",P.ans);

     }

     return ;

 }