YellowStar拥有一棵神奇的动态树，该树由n个带权结点，n-1条边构成，任意两个结点互相可达，标号为i结点的权值为Wi。

由于物质是运动的，这棵树每天都会发生一些变化，在第i天，该树权值在[l,r]的结点会发出强烈的光芒，YellowStar看到这一现象会非常的愉悦，它的愉悦值取决于：发光的这些结点构成了多少个连通子树。

现在你知道动态树在接下来m天的发光情况，请你计算出YellowStar每一天的愉悦值

第一行输入T，表示有T组样例(T <= 20)

每组样例第一行为n，表示树的结点个数(1 <= n <= 1e5)

接下来n个数字W1, W2, ... , Wn (1 <= Wi <= 1e9)表示每个结点的权值

接下来n - 1行，每一行两个数字u, v (1 <= u, v <= n)表示树边

接下来一个数字m(1 <= m <= 1e5)，表示m天

接下来m个询问,每个询问一行l, r (1 <= l <= r <= 1e9)表示每一天发光的结点的权值区间

#include <cstdio>

#include <vector>

#include <cstring>

#include <string>

#include <cstdlib>

#include <iostream>

#include <map>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long LL;

typedef pair<int,int>pii;

const int N = 1e5+;

const double eps = 1e-;

int T,n,w[N],sum[N<<],p[N<<],cnt,m,ret[N],c[N<<];

struct Query{

  int l,r,id;

  bool operator<(const Query &rhs)const{

      return r<rhs.r;

  }

}q[N],t[N];

void add(int x){

   for(;x<=cnt;x+=x&-x)++c[x];

}

int ask(int x){

   int ret = ;

   for(;x>;x-=x&-x)ret+=c[x];

   return ret;

}

int main() {

   scanf("%d",&T);

   while(T--){

     scanf("%d",&n);

     cnt = ;

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

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

       p[++cnt]=w[i];

     }

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

        scanf("%d%d",&t[i].l,&t[i].r);

        t[i].l=w[t[i].l];

        t[i].r=w[t[i].r];

     }

     scanf("%d",&m);

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

        scanf("%d%d",&q[i].l,&q[i].r);

        p[++cnt]=q[i].l;

        p[++cnt]=q[i].r;

        q[i].id=i;

     }

     sort(p+,p++cnt);

     cnt=unique(p+,p++cnt)-p-;

     for(int i=;i<=cnt;++i)c[i]=sum[i]=;

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

        w[i]=lower_bound(p+,p++cnt,w[i])-p;

        ++sum[w[i]];

     }

     for(int i=;i<=cnt;++i)sum[i]+=sum[i-];

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

        t[i].l=lower_bound(p+,p++cnt,t[i].l)-p;

        t[i].r=lower_bound(p+,p++cnt,t[i].r)-p;

        if(t[i].l>t[i].r)swap(t[i].l,t[i].r);

     }

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

        q[i].l=lower_bound(p+,p++cnt,q[i].l)-p;

        q[i].r=lower_bound(p+,p++cnt,q[i].r)-p;

     }

     if(n!=)sort(t+,t++n-);

     sort(q+,q++m);

     int j=;

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

       ret[q[i].id]=sum[q[i].r]-sum[q[i].l-];

       for(;j<=n-&&t[j].r<=q[i].r;++j)add(t[j].l);

       ret[q[i].id]-=ask(q[i].r)-ask(q[i].l-);

     }

     for(int i=;i<=m;++i)printf("%d\n",ret[i]);

   }

   return ;

}