水果姐逛水果街II——又又一个LCA

 1 #include<iostream>
 2 #include<vector>
 3 #include<cstdio>
 4 #define F ast[x][i-1]
 5 using namespace std;
 6 const int N=200010;
 7 //Constants;//
 8 int n,m,val[N];
 9 vector<int> gr[N];
10 //INput;//
11 int ans,ast[N][18],depth[N],mxv[N][18],mnv[N][18],up[N][18],dn[N][18];
12 bool vis[N];
13 //Usage;//
14 
15 void dfs(int x){
16     vis[x]=true;
17     for(int i=1;i<=18;i++){
18         if(depth[x]<(1<<i))break;
19         ast[x][i]=ast[F][i-1];
20         
21         mxv[x][i]=max(mxv[x][i-1],mxv[F][i-1]);
22         mnv[x][i]=min(mnv[x][i-1],mnv[F][i-1]);
23         
24         up[x][i]=max(max(up[x][i-1],up[F][i-1]),mxv[F][i-1]-mnv[x][i-1]);
25         dn[x][i]=max(max(dn[x][i-1],dn[F][i-1]),mxv[x][i-1]-mnv[F][i-1]);
26     }
27     
28     for(int i=0;i<gr[x].size();i++)
29         if(!vis[gr[x][i]]){
30             int v=gr[x][i];
31             ast[v][0]=x;
32             depth[v]=depth[x]+1;
33             
34             mxv[v][0]=max(val[v],val[x]);
35             mnv[v][0]=min(val[v],val[x]);
36             
37             up[v][0]=val[x]-val[v];
38             dn[v][0]=val[v]-val[x];
39             
40             dfs(v);
41         }
42 }
43 
44 int lca(int x,int y){
45     if(depth[x]<depth[y])swap(x,y);
46     int k=depth[x]-depth[y];
47     for(int i=0;i<=18;i++)
48         if(k&(1<<i))
49             x=ast[x][i];
50     
51     for(int i=18;i>=0;i--)
52         if(ast[x][i]!=ast[y][i])
53             x=ast[x][i],y=ast[y][i];
54     
55     if(x==y)return x;
56     return ast[x][0];
57 }
58 
59 int calculate(int x,int y){
60     int maxn=0,minn=0x7fffffff,pnt=lca(x,y),k;
61     ans=0;
62     k=depth[x]-depth[pnt];
63     if(k>0){
64         for(int i=0;i<=18;i++)
65             if(k&(1<<i)){
66                 ans=max(ans,max(mxv[x][i]-minn,up[x][i]));
67                 minn=min(minn,mnv[x][i]);
68                 x=ast[x][i];
69             }
70     }
71     k=depth[y]-depth[pnt];
72     if(k>0){
73         for(int i=0;i<=18;i++)
74             if(k&(1<<i)){
75                 ans=max(ans,max(maxn-mnv[y][i],dn[y][i]));
76                 maxn=max(maxn,mxv[y][i]);
77                 y=ast[y][i];
78             }
79     }
80     ans=max(ans,maxn-minn);
81 }
82 //Function(s);//
83 int main(){
84     cin>>n;
85     for(int i=1;i<=n;i++)cin>>val[i];
86     for(int i=1;i<n;i++){
87         int x,y;cin>>x>>y;
88         gr[x].push_back(y);gr[y].push_back(x);
89     }
90     ast[1][0]=1;
91     dfs(1);
92     cin>>m;
93     while(m--){
94         int x,y;cin>>x>>y;
95         calculate(x,y);
96         cout<<ans<<endl;
97     }
98     return 0;
99 }