Motoku2

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ZERO (1e-10)
#define INF int(1e9+1)
#define CL(A,I) (memset(A,I,sizeof(A)))
#define DEB printf("DEB!\n");
#define D(X) cout<<"  "<<#X": "<<X<<endl;
#define EQ(A,B) (A+ZERO>B&&A-ZERO<B)
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<pll> vii;
#define IN(n) int n;scanf("%d",&n);
#define FOR(i, m, n) for (int i(m); i < n; i++)
#define F(n) FOR(i,0,n)
#define FF(n) FOR(j,0,n)
#define FT(m, n) FOR(k, m, n)
#define aa first
#define bb second
void ga(int N,int *A){F(N)scanf("%d",A+i);}
#define MX (300666)
vi g[MX];
int W[MX];
void foo(int);
int dfs(int u,int p){
    W[u]=1;
    for(auto&h:g[u])if(h^p)W[u]+=dfs(h,u);
    return W[u];
}
int rot(int u,int S){
    for(auto&h:g[u])if(W[h]>S-W[h]&&W[h]<W[u])return rot(h,S);
    return u;
}
void cdc(int r=0){
    int S=dfs(r,-1),R=rot(r,S);
    foo(R);
    for(auto&h:g[R]){
        for(auto&w:g[h])if(w==R)w=g[h].back();
        g[h].pop_back();
        cdc(h);
        g[h].PB(R);
    }
}
#define ADD(A,B) (g[A].PB(B),g[B].PB(A))
int N,A[MX],a,b,l;
ll O[MX],S[MX],s[MX],z[MX],Z[MX];
vii Q[MX];
void add(int d,ll T,int m){
    if(S[d]>T){
        if(Z[d]==m)S[d]=T;
        else z[d]=Z[d],s[d]=S[d],S[d]=T,Z[d]=m;
    }else if(Z[d]==m)return;
    else if(s[d]>T)s[d]=T,z[d]=m;
}
ll dis(int d,int m){
    return Z[d]^m?S[d]:s[d];
}
void pud(int u,int d,ll T,int p,int m,int&l){
    T+=A[u],l=max(l,d),add(d,T,m);
    for(auto&h:g[u])if(h^p)pud(h,d+1,T,u,m,l);
}
void bst(int u,int d,ll T,int p,int m){
    T+=A[u];
    for(auto&h:Q[u])if(h.aa>=d)O[h.bb]=min(O[h.bb],T+dis(h.aa-d,m));
    for(auto&h:g[u])if(h^p)bst(h,d+1,T,u,m);
}
void foo(int r){
    l=0,*S=0,*Z=-1;
    F((int)g[r].size())pud(g[r][i],1,0,r,i,l);
    ++l;
    F((int)g[r].size())bst(g[r][i],1,A[r],r,i);
    for(auto&h:Q[r])O[h.bb]=min(O[h.bb],A[r]+dis(h.aa,-2));
    F(l)S[i]=s[i]=z[i]=Z[i]=1e17;
}
int main(void){
    scanf("%d",&N),ga(N,A),fill(O,O+MX,1e18);
    F(MX)S[i]=s[i]=z[i]=Z[i]=1e17;
    F(N-1)scanf("%d%d",&a,&b),--a,--b,ADD(a,b);
    IN(_)F(_)scanf("%d%d",&a,&b),Q[--a].PB({b,i});
    cdc();
    F(_)printf("%lld\n",O[i]<1e15?O[i]:-1);
    return 0;
}