#include<bits/stdc++.h> #define int long long #define lc(p) ((p)<<1) #define rc(p) ((p)<<1|1) #define endl '\n' using namespace std; const int N=2e5+7; int n,m,a[N]; vector<int> E[N]; int d[N],f[N],h[N],t[N],siz[N]; inline void DFS1(int u){ d[u]=d[f[u]]+1; siz[u]=1; for(auto v:E[u]){ if(v==f[u])continue; f[v]=u;DFS1(v); siz[u]+=siz[v]; if(siz[v]>siz[h[u]])h[u]=v; } } inline void DFS2(int u,int tp){ t[u]=tp; if(!h[u])return; DFS2(h[u],tp); for(auto v:E[u]){ if(v==f[u]||v==h[u])continue; DFS2(v,v); } } inline int LCA(int u,int v){ while(t[u]!=t[v]){ if(d[t[u]]>d[t[v]])u=f[t[u]]; else v=f[t[v]]; }return d[u]<d[v]?u:v; } inline int Dis(int u,int v){ return d[u]+d[v]-2*d[LCA(u,v)]; } inline int XD(int u,int v){return (a[u]+a[v]+Dis(u,v));} struct Node{ int P1,P2; inline int Val()const{return XD(P1,P2);} }; inline bool operator>(const Node &x,const Node &y){return x.Val()>y.Val();} inline bool operator<(const Node &x,const Node &y){return x.Val()<y.Val();} struct SGT{ Node d[N<<2]; inline void pu(int p){ d[p]=max(d[lc(p)],d[rc(p)]); d[p]=max(d[p],max((Node){d[lc(p)].P1,d[rc(p)].P1},(Node){d[lc(p)].P1,d[rc(p)].P2})); d[p]=max(d[p],max((Node){d[lc(p)].P2,d[rc(p)].P1},(Node){d[lc(p)].P2,d[rc(p)].P2})); } inline void Build(int p,int l,int r){ if(l==r)return void(d[p]=(Node){l,l}); int mid=l+r>>1; Build(lc(p),l,mid);Build(rc(p),mid+1,r); pu(p); } inline void Upd(int p,int l,int r,int x,int v){ if(l==r)return void(a[x]=v); int mid=l+r>>1; if(x<=mid)Upd(lc(p),l,mid,x,v); if(x>mid)Upd(rc(p),mid+1,r,x,v); pu(p); } }T; signed main(){ #ifndef ONLINE_JUDGE freopen("award.in","r",stdin); freopen("award.out","w",stdout); #endif cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<n;i++){ int u,v;cin>>u>>v; E[u].push_back(v);E[v].push_back(u); } cin>>m; DFS1(1); DFS2(1,1); T.Build(1,1,n); while(m--){ int p,x;cin>>p>>x; T.Upd(1,1,n,p,x); cout<<max((T.d[1].Val()+1)/2,max(a[T.d[1].P1],a[T.d[1].P2]))<<endl; } cout.flush(); return 0; }