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.

The first line contains N, the number of cities.
Each of the next N lines contains w_i 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, w_i, Q ≤ 50000

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

  1 #include <iostream>

  2 #include <algorithm>

  3 #include <cstring>

  4 #define ll long long

  5 #define ull unsigned long long

  6 #define ms(a,b) memset(a,b,sizeof(a))

  7 const int inf=0x3f3f3f3f;

  8 const ll INF=0x3f3f3f3f3f3f3f3f;

  9 const int maxn=1e6+10;

 10 const int mod=1e9+7;

 11 const int maxm=1e3+10;

 12 using namespace std;

 13 int maxx[maxn],minn[maxn];

 14 int up[maxn],down[maxn];

 15 int f[maxn];

 16 // minn[u]        u->lca(u,v)买的最小值

 17 // maxx[v]        lca(u,v)->v卖的最大值

 18 // up[u]           u->lca(u,v)进行买卖的最大值

 19 // down[v]       lca(u,v)->v进行买卖的最大值

 20 int find(int x)

 21 {

 22     if(f[x]==x)

 23         return x;

 24     int y=f[x];

 25     f[x]=find(f[x]);

 26     up[x]=max(max(up[y],up[x]),maxx[y]-minn[x]);

 27     down[x]=max(max(down[y],down[x]),maxx[x]-minn[y]);

 28     maxx[x]=max(maxx[x],maxx[y]);

 29     minn[x]=min(minn[x],minn[y]);

 30     return f[x];

 31 }

 32 void join(int x,int y)

 33 {

 34     int dx=f[x],dy=f[y];

 35     if(dx!=dy)

 36         f[y]=dx;

 37 }

 38 struct Edge

 39 {

 40     int to,Next;

 41 }edge[maxn];

 42 int head1[maxn];

 43 int tot1;

 44 void add_edge(int u,int v)

 45 {

 46     edge[tot1].to=v;

 47     edge[tot1].Next=head1[u];

 48     head1[u]=tot1++;

 49 }

 50 struct Query

 51 {

 52     int to,Next;

 53     int index;

 54 }query[maxn];

 55 int head2[maxn];

 56 int tot2;

 57 void add_query(int u,int v,int index)

 58 {

 59     query[tot2].to=v;

 60     query[tot2].Next=head2[u];

 61     query[tot2].index=index;

 62     head2[u]=tot2++;

 63 }

 64 struct Pos

 65 {

 66     int to,Next;

 67     int index;

 68 }pos[maxn];

 69 int head3[maxn];

 70 int tot3;

 71 void add_pos(int u,int v,int index)

 72 {

 73     pos[tot3].to=v;

 74     pos[tot3].Next=head3[u];

 75     pos[tot3].index=index;

 76     head3[u]=tot3++;

 77 }

 78 int vis[maxn];

 79 int qu[maxn],qv[maxn];

 80 int fa[maxn];

 81 int ans[maxn];

 82 void LCA(int u)

 83 {

 84     fa[u]=u;

 85     vis[u]=1;

 86     for(int i=head1[u];~i;i=edge[i].Next)

 87     {

 88         int v=edge[i].to;

 89         if(vis[v])

 90             continue;

 91         LCA(v);

 92         join(u,v);

 93         fa[find(u)]=u;

 94     }

 95     for(int i=head2[u];~i;i=query[i].Next)

 96     {

 97         int v=query[i].to;

 98         if(vis[v])

 99         {

100             int t=fa[find(v)];

101             // 储存lca(u,v)的子节点

102             add_pos(t,v,query[i].index);

103         }

104     }

105     for(int i=head3[u];~i;i=pos[i].Next)

106     {

107         int id=pos[i].index;

108         int xx=qu[id],yy=qv[id];

109         // 更新四个数组的值

110         find(xx);find(yy);

111         ans[id]=max(max(up[xx],down[yy]),maxx[yy]-minn[xx]);

112     }

113 }

114 int value[maxn];

115 void init(int n)

116 {

117     tot1=0;tot2=0;tot3=0;

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

119         f[i]=i;

120     ms(fa,0);ms(vis,0);

121     ms(head1,-1);ms(head2,-1);ms(head3,-1);

122 }

123 int main(int argc, char const *argv[])

124 {

125     #ifndef ONLINE_JUDGE

126         freopen("/home/wzy/in.txt", "r", stdin);

127         freopen("/home/wzy/out.txt", "w", stdout);

128         srand((unsigned int)time(NULL));

129     #endif

130     ios::sync_with_stdio(false);

131     cin.tie(0);

132     int n;

133     cin>>n;

134     init(n);

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

136         cin>>value[i],minn[i]=value[i],maxx[i]=value[i];

137     int u,v;

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

139         cin>>u>>v,add_edge(u,v),add_edge(v,u);

140     int q;

141     cin>>q;

142     for(int i=0;i<q;i++)

143         cin>>qu[i]>>qv[i],add_query(qu[i],qv[i],i),add_query(qv[i],qu[i],i);

144     LCA(1);

145     for(int i=0;i<q;i++)

146         cout<<ans[i]<<"\n";

147     #ifndef ONLINE_JUDGE

148         cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;

149     #endif

150     return 0;

151 }