# pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using i128=__int128;
constexpr int inf=1e9;
constexpr ll INF=2e18;
#define rep(i,n) for(ll i=0;i<ll(n);i++)
#define REP(i,n,m) for(ll i=(n);i<ll(m);i++)
#define DREP(i,n,m) for(ll i=(n);i>=ll(m);i--)
#define drep(i,n) for(ll i=ll(n)-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
template<class T>using vvvc=vc<vc<vc<T>>>;
template<class T>using vvvvc=vc<vc<vc<vc<T>>>>;
template<class T>using smpq=priority_queue<T,vc<T>,greater<T>>;
template<class T>using bipq=priority_queue<T>;
template<class T,class F>
int chmin(T&a,F b){
    if(a>b){
        a=b;
        return 1;
    }
    return 0;
}
template<class T,class F>
int chmax(T&a,F b){
    if(a<b){
        a=b;
        return 1;
    }
    return 0;
}
#ifndef ATCODER
// pair
template<typename T, typename U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
    return os << "(" << p.first << ", " << p.second << ")";
}
// vector
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    os << "[";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i > 0) os << ", ";
        os << v[i];
    }
    os << "]";
    return os;
}

// deque
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::deque<T>& dq) {
    os << "[";
    for (size_t i = 0; i < dq.size(); ++i) {
        if (i > 0) os << ", ";
        os << dq[i];
    }
    os << "]";
    return os;
}

// list
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::list<T>& lst) {
    os << "[";
    bool first = true;
    for (const auto& x : lst) {
        if (!first) os << ", ";
        os << x;
        first = false;
    }
    os << "]";
    return os;
}

// set
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
    os << "{";
    bool first = true;
    for (const auto& x : s) {
        if (!first) os << ", ";
        os << x;
        first = false;
    }
    os << "}";
    return os;
}

// unordered_set
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::unordered_set<T>& s) {
    os << "{";
    bool first = true;
    for (const auto& x : s) {
        if (!first) os << ", ";
        os << x;
        first = false;
    }
    os << "}";
    return os;
}

// map
template<typename K, typename V>
std::ostream& operator<<(std::ostream& os, const std::map<K, V>& m) {
    os << "{";
    bool first = true;
    for (const auto& kv : m) {
        if (!first) os << ", ";
        os << kv;
        first = false;
    }
    os << "}";
    return os;
}

// unordered_map
template<typename K, typename V>
std::ostream& operator<<(std::ostream& os, const std::unordered_map<K, V>& m) {
    os << "{";
    bool first = true;
    for (const auto& kv : m) {
        if (!first) os << ", ";
        os << kv;
        first = false;
    }
    os << "}";
    return os;
}

// stack（コピーが必要）
template<typename T>
std::ostream& operator<<(std::ostream& os, std::stack<T> st) {
    os << "[";
    bool first = true;
    while (!st.empty()) {
        if (!first) os << ", ";
        os << st.top();
        st.pop();
        first = false;
    }
    os << "]";
    return os;
}

// queue（コピーが必要）
template<typename T>
std::ostream& operator<<(std::ostream& os, std::queue<T> q) {
    os << "[";
    bool first = true;
    while (!q.empty()) {
        if (!first) os << ", ";
        os << q.front();
        q.pop();
        first = false;
    }
    os << "]";
    return os;
}

// priority_queue（コピーが必要）
template<typename T>
std::ostream& operator<<(std::ostream& os, std::priority_queue<T> pq) {
    os << "[";
    bool first = true;
    while (!pq.empty()) {
        if (!first) os << ", ";
        os << pq.top();
        pq.pop();
        first = false;
    }
    os << "]";
    return os;
}

#define dbg(...) debug_func(0, #__VA_ARGS__, __VA_ARGS__)

template <typename T>
void debug_func(int i, T name) {
  cout << endl;
}

template <typename T1, typename T2, typename... T3>
void debug_func(int i, const T1 &name, const T2 &a, const T3 &...b) {
  for ( ; name[i] != ',' && name[i] != '\0'; i++ ) cout << name[i];
  cout << ":" << a << " ";
  debug_func(i + 1, name, b...);
}
#else
#define dbg(...) 123456789
#endif
template<class T>
vc<T>sorted(vc<T>v){
    sort(all(v));
    return v;
}
template<class T>
vc<T>reved(vc<T>v){
    reverse(all(v));
    return v;
}
template<class T>
vc<T>presum(vc<T>v){
    vc<T>res(v.size()+1);
    rep(i,v.size()){
      res[i+1]=res[i]+v[i];
    }
    return res;
}


template <typename T>
struct edge {
  int src, to;
  T cost;

  edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}
  edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnweightedGraph = vector<vector<int>>;

// Input of (Unweighted) Graph
UnweightedGraph graph(int N, int M = -1, bool is_directed = false,
                      bool is_1origin = true) {
  UnweightedGraph g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    if (is_1origin) x--, y--;
    g[x].push_back(y);
    if (!is_directed) g[y].push_back(x);
  }
  return g;
}

// Input of Weighted Graph
template <typename T>
WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false,
                        bool is_1origin = true) {
  WeightedGraph<T> g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    cin >> c;
    if (is_1origin) x--, y--;
    g[x].emplace_back(x, y, c);
    if (!is_directed) g[y].emplace_back(y, x, c);
  }
  return g;
}

// Input of Edges
template <typename T>
Edges<T> esgraph([[maybe_unused]] int N, int M, int is_weighted = true,
                 bool is_1origin = true) {
  Edges<T> es;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    es.emplace_back(x, y, c);
  }
  return es;
}

// Input of Adjacency Matrix
template <typename T>
vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true,
                           bool is_directed = false, bool is_1origin = true) {
  vector<vector<T>> d(N, vector<T>(N, INF));
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    d[x][y] = c;
    if (!is_directed) d[y][x] = c;
  }
  return d;
}

/**
 * @brief グラフテンプレート
 * @docs docs/graph/graph-template.md
 */

template <typename G>
struct Tree {
 private:
  G& g;
  int root;
  vector<array<int, 24>> bl;
  vector<int> dp;
  void build() {
    bl.resize(g.size());
    dp.resize(g.size());
    for (auto& v : bl) fill(begin(v), end(v), -1);
    dfs(root, -1, 0);
  }

  void dfs(int c, int p, int _dp) {
    dp[c] = _dp;
    for (int i = p, x = 0; i != -1;) {
      bl[c][x] = i;
      i = bl[i][x], x++;
    }
    for (auto& d : g[c]) {
      if (d == p) continue;
      dfs(d, c, _dp + 1);
    }
  }

 public:
  Tree(G& _g, int _r = 0) : g(_g), root(_r) { build(); }

  int depth(int u) const { return dp[u]; }

  int par(int u) const { return u == root ? -1 : bl[u][0]; }

  int kth_ancestor(int u, int k) const {
    if (dp[u] < k) return -1;
    while (k) {
      int t = __builtin_ctz(k);
      u = bl[u][t], k ^= 1 << t;
    }
    return u;
  }

  int nxt(int s, int t) const {
    if (dp[s] >= dp[t]) return par(s);
    int u = kth_ancestor(t, dp[t] - dp[s] - 1);
    return bl[u][0] == s ? u : bl[s][0];
  }

  vector<int> path(int s, int t) const {
    vector<int> pre, suf;
    while (dp[s] > dp[t]) {
      pre.push_back(s);
      s = bl[s][0];
    }
    while (dp[s] < dp[t]) {
      suf.push_back(t);
      t = bl[t][0];
    }
    while (s != t) {
      pre.push_back(s);
      suf.push_back(t);
      s = bl[s][0];
      t = bl[t][0];
    }
    pre.push_back(s);
    reverse(begin(suf), end(suf));
    copy(begin(suf), end(suf), back_inserter(pre));
    return pre;
  }

  int lca(int u, int v) {
    if (dp[u] != dp[v]) {
      if (dp[u] > dp[v]) swap(u, v);
      v = kth_ancestor(v, dp[v] - dp[u]);
    }
    if (u == v) return u;
    for (int i = __lg(dp[u]); i >= 0; --i) {
      if (dp[u] < (1 << i)) continue;
      if (bl[u][i] != bl[v][i]) u = bl[u][i], v = bl[v][i];
    }
    return bl[u][0];
  }

  // u - v 間のパス上の頂点のうち u から距離 i の頂点
  // (dist(u, v) < i のとき -1)
  int jump(int u, int v, int i) {
    int lc = lca(u, v);
    int d1 = dp[u] - dp[lc];
    if (i <= d1) return kth_ancestor(u, i);
    int d = d1 + dp[v] - dp[lc];
    if (i <= d) return kth_ancestor(v, d - i);
    return -1;
  }
};

template<class T = long long >
struct BIT {
    int n;
    std::vector<T>data;
    BIT():n(0), data(0) {}
    BIT(int N):n(N), data(N) {}
    BIT(vector<T>& N) {
        data = N;
        n = N.size();
    }
    void add(int i,T x){
        assert(i>=0&&i<n);
        i++;
        for(;i<=n;){
            data[i - 1] += x;
            i += (i & -i);
        }
        return;
    }   
    T internal_sum(int r){
        T ret = 0;
        for(;r;){
            ret += data[r - 1];
            r -= (r & -r);
        }
        return ret;
    }
    T sum(int l,int r){
        return internal_sum(r)-internal_sum(l);
    }
};
/**
 * @brief 木に対する一般的なクエリ
 * @docs docs/tree/tree-query.md
 */
#include <utility>
#include <vector>
#include <algorithm>


using Elem=int;
class CsrArray{
public:
    struct ListRange{
        using iterator = typename std::vector<Elem>::iterator;
        iterator begi, endi;
        iterator begin() const { return begi; }
        iterator end() const { return endi; }
        int size() const { return (int)std::distance(begi, endi); }
        Elem& operator[](int i) const { return begi[i]; }
    };
    struct ConstListRange{
        using iterator = typename std::vector<Elem>::const_iterator;
        iterator begi, endi;
        iterator begin() const { return begi; }
        iterator end() const { return endi; }
        int size() const { return (int)std::distance(begi, endi); }
        const Elem& operator[](int i) const { return begi[i]; }
    };
private:
    int m_n;
    std::vector<Elem> m_list;
    std::vector<int> m_pos;
public:
    CsrArray() : m_n(0), m_list(), m_pos() {}
    static CsrArray Construct(int n, std::vector<std::pair<int, Elem>> items){
        CsrArray res;
        res.m_n = n;
        std::vector<int> buf(n+1, 0);
        for(auto& [u,v] : items){ ++buf[u]; }
        for(int i=1; i<=n; i++) buf[i] += buf[i-1];
        res.m_list.resize(buf[n]);
        for(int i=(int)items.size()-1; i>=0; i--){
            res.m_list[--buf[items[i].first]] = std::move(items[i].second);
        }
        res.m_pos = std::move(buf);
        return res;
    }
    static CsrArray FromRaw(std::vector<Elem> list, std::vector<int> pos){
        CsrArray res;
        res.m_n = pos.size() - 1;
        res.m_list = std::move(list);
        res.m_pos = std::move(pos);
        return res;
    }
    ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
    ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
    int size() const { return m_n; }
    int fullSize() const { return (int)m_list.size(); }
};
// namespace nachia
struct ds{
    static const int B=50;
    static const int B2=B*B;
    array<vc<int>,3>block,pref;
    static const int N=B*B*B;
    vc<pair<int,int>>hist;
    ds(int n){
        assert(n<=B*B*B);
        rep(i,3){
            block[i]=pref[i]=vc<int>(N);
        }
    }
    void add(int i,int x,bool reset=false){
        if(!reset)hist.push_back({i,x});
        rep(t,3){
            block[t][i]+=x;
            bool first=true;
            REP(j,i/B*B,(i/B+1)*B){
                pref[t][j]=block[t][j];
                if(!first){
                    pref[t][j]+=pref[t][j-1];
                }else{
                    first=false;
                }
            }
            i/=B;
        }
    }
    void rollback(){
        auto&[x,y]=hist.back();add(x,-y,1);
        hist.pop_back();
    }
    void reset(){
        for(auto&[x,y]:hist)add(x,-y,1);
        hist.clear();
    }
    //[0,x)
    int sum(int x){
        int res=0;
        rep(t,3){
            res+=x%B?pref[t][x-1]:0;
            x/=B;
        }
        return res;
    }
    int sum(int l,int r){
        return sum(r)-sum(l);
    }
};

CsrArray g;
int id[(int)5e4];
int going[(int)5e4];
int from_leader[250][(int)5e4];
int to_leader[250][(int)5e4];
struct CALC{
    vc<int>vs;
    vc<int>a;
    int n;
    CALC(int n,vc<int>vs):n(n),a(n),vs(vs){}

    void set(int i,int x){
        a[i]=x;
    }
    vvc<ll>calc(){
        rep(i,vs.size())id[vs[i]]=i;
        for(auto&x:vs)going[x]=1;
        vvc<ll>ans(n,vc<ll>(n,-1e9));//i -> j の転倒数
        vvc<ll>over(n,vc<ll>(n,-1e9));//i -> j で a_j より大きいものの個数
        for(auto&x:vs){
            auto dfs=[&](auto&dfs,int u,int p)->void{
                if(p!=-1){
                    over[id[u]][id[x]]=over[id[p]][id[x]]+(a[id[x]]<a[id[u]]);
                }
                for(auto&x:g[u]){
                    if(x==p)continue;
                    if(!going[x])continue;
                    dfs(dfs,x,u);
                }
            };
            over[id[x]][id[x]]=0;
            dfs(dfs,x,-1);
        }
        for(auto&x:vs){
            ans[id[x]][id[x]]=0;
            auto dfs=[&](auto&dfs,int u,int p)->void{
                if(p!=-1){
                    ans[id[x]][id[u]]=over[id[x]][id[u]]+ans[id[x]][id[p]];
                }
                for(auto&x:g[u]){
                    if(x==p)continue;
                    if(!going[x])continue;
                    dfs(dfs,x,u);
                }
            };
            dfs(dfs,x,-1);
        }
        for(auto&x:vs)going[x]=0;
        return ans;
    }
};  
struct Onl{
    int n;
    BIT<int>bit;
    ll inv;
    vc<pair<int,int>>hist;
    Onl(int n):n(n),bit(n),inv(0){}
    void add(int i,int x,bool reset=false){
        if(!reset)hist.push_back({i,x});
        bit.add(i,x);
        inv+=bit.sum(i+1,n)*(reset?-1:1);
    }
    void rollback(){
        auto&[i,x]=hist.back();
        add(i,-x,1);
        hist.pop_back();
    }  
};
struct Onl2{
    int n;
    BIT<int>bit;
    ll inv;
    vc<pair<int,int>>hist;
    Onl2(int n):n(n),bit(n),inv(0){}
    void add(int i,int x,bool reset=false){
        if(!reset)hist.push_back({i,x});
        bit.add(i,x);
        inv+=bit.sum(0,i)*(reset?-1:1);
    }
    void rollback(){
        auto&[i,x]=hist.back();
        add(i,-x,1);
        hist.pop_back();
    }  
};
vc<ll> solve(int n,vc<pair<int,int>>e,vc<int>A,vc<pair<int,int>>Q,bool lock=true){
    for(auto&x:e)x.first--,x.second--;
    for(auto&x:A)x--;
    {
        vc<pair<int,int>>ne=e;for(auto&x:e)ne.push_back({x.second,x.first});
        g=CsrArray::Construct(n,ne);
    }
    vvc<int>G(n);rep(i,n-1)G[e[i].first].push_back(e[i].second),G[e[i].second].push_back(e[i].first);

    Tree tree(G);
    vc<int>leader;//i th leader 
    vc<int>group(n,-1);//leader of vertex i 
    vc<int>sub_id(n,-1);//id in subtree
    vc<int>sub_size;//size of subtree i
    vvc<int>subs;//vertexs of i th subtree
    vc<int>bel_sub(n,-1);//subtree vertex i belong
    vvvc<ll>inv_sub;//inv between same subtree
    vvc<int>sorted_seq(n);//leader to i sorted 
    int SQRT=sqrt(n);
    //get leader inf
    {
        auto push=[&](vc<int>g){
            int gid=leader.size();
            leader.push_back(g[0]);
            for(auto&x:g){
                group[x]=gid;
            }
        };
        vvc<int>res(n);
        auto dfs=[&](auto&dfs,int u,int p)->void{
            auto&tar=res[u];
            res[u].push_back(u);
            for(auto&x:g[u]){
                if(x==p)continue;
                dfs(dfs,x,u);
                for(auto&e:res[x]){
                    tar.push_back(e);
                }
            }
            if(tar.size()>=SQRT){
                push(tar);
                tar={};
            }
            return;
        };  
        dfs(dfs,0,-1);
        auto re=res[0];
        if(re.size())push(re);
    }
    //get subtree inf
    {
        
        for(auto&x:leader){
            for(auto&nx:g[x]){
                if(group[nx]==group[x]){
                    int sid=sub_size.size();
                    int id_insb=0;
                    sub_size.push_back({});
                    subs.push_back({});
                    auto dfs=[&](auto&dfs,int u,int p)->void{
                        sub_size[sid]++;
                        sub_id[u]=id_insb++;
                        bel_sub[u]=sid;
                        subs.back().push_back(u);
                        for(auto&to:g[u]){
                            if(to==p)continue;
                            if(group[to]!=group[u])continue;
                            dfs(dfs,to,u);
                        }
                    };
                    dfs(dfs,nx,x);
                }
            }
        }
    }
    //inv in subtree
    {
        inv_sub.resize(subs.size());
        rep(i,subs.size()){
            CALC calc(subs[i].size(),subs[i]);
            int cnt=0;
            for(auto&x:subs[i]){
                calc.set(sub_id[x],A[x]);
            }
            inv_sub[i]=calc.calc();
        }
    }
    //get all sorted
        auto insert=[&](vc<int>&res,int k){
            rep(i,res.size())if(res[i]>k){
                res.insert(res.begin()+i,k);
                return;
            }
            res.push_back(k);
        };
        auto erase=[&](vc<int>&res,int k){
            rep(i,res.size())if(res[i]==k){
                res.erase(res.begin()+i);
                return;
            }
            assert(0);
        };
        for(auto&x:leader){
            vc<int>res;
            auto dfs=[&](auto&dfs,int u,int p)->void{
                if(u!=x)insert(res,A[u]);
                sorted_seq[u]=res;
                for(auto&to:g[u]){
                    if(to==p)continue;
                    if(group[to]!=group[u])continue;
                    dfs(dfs,to,u);
                }
                if(u!=x)erase(res,A[u]);
            };
            dfs(dfs,x,-1);
        }
    {
        vc<int>alive(n,1);
        vc<int>size(n);
        ds ds(n);
        vc<ll>tmp1(n),tmp2(n);
        Onl onl1(n);
        Onl2 onl2(n);
        auto decomposition=[&](auto&decomposition,int x)->void{
            //find centroid 
            {auto dfs=[&](auto&dfs,int x,int p)->void{
                size[x]=1;
                bool is_c=1;
                for(auto&to:g[x]){
                    if(to==p)continue;
                    if(!alive[to])continue;
                    dfs(dfs,to,x);
                    size[x]+=size[to];
                }
            };
            dfs(dfs,x,-1);}
            int N=size[x];
            int c=-1;
            {
            auto dfs=[&](auto&dfs,int x,int p)->void{
                bool is_c=1;
                for(auto&to:g[x]){
                    if(to==p)continue;
                    if(!alive[to])continue;
                    dfs(dfs,to,x);
                    if(size[to]>N/2)is_c=0;
                }
                if(N-size[x]>N/2)is_c=0;
                if(is_c)c=x;
            };
            dfs(dfs,x,-1);
            }
            //get_inv
            {
                auto dfs=[&](auto&dfs,int u,int p)->void{
                    onl1.add(A[u],1);
                    onl2.add(A[u],1);
                    tmp1[u]=onl1.inv;
                    tmp2[u]=onl2.inv;
                    for(auto&to:g[u]){
                        if(to==p)continue;
                        if(!alive[to])continue;
                        dfs(dfs,to,u);
                    }
                    onl1.rollback();
                    onl2.rollback();
                };
                dfs(dfs,c,-1);
            }
            vc<int>has_leader(g[c].size());
            rep(i,g[c].size()){
                auto dfs=[&](auto&dfs,int u,int p)->bool{
                    if(u==leader[group[u]])return 1;
                    for(auto&to:g[u]){
                        if(to==p)continue;
                        if(!alive[to])continue;
                        if(dfs(dfs,to,u))return 1;
                    }
                    return 0;
                };
                if(alive[g[c][i]])has_leader[i]=dfs(dfs,g[c][i],c);
            }
            vc<int>leader_idx;
            rep(i,g[c].size())if(has_leader[i])leader_idx.push_back(i);
            auto push=[&](int x,int i){
                int true_idx;
                bool f=1;
                int L;
                auto dfs2=[&](auto&dfs2,int u,int p,ll inv1,ll inv2)->void{
                    from_leader[true_idx][u]=(inv1+=ds.sum(A[u]+1,n))+tmp1[u]+tmp2[L];
                    to_leader[true_idx][u]=(inv2+=ds.sum(0,A[u]))+tmp2[u]+tmp1[L];
                    for(auto&to:g[u]){
                        if(to==p)continue;
                        if(!alive[to])continue;
                        dfs2(dfs2,to,u,inv1,inv2);
                    }
                };
                auto dfs1=[&](auto&dfs1,int u,int p)->void{
                    ds.add(A[u],1);
                    if(leader[group[u]]==u){
                        true_idx=group[u];
                        L=leader[true_idx];
                        rep(j,g[c].size()){
                            int to=g[c][j];
                            if(alive[to]&&i!=j)dfs2(dfs2,to,c,0,0);
                        }
                        from_leader[true_idx][c]=tmp2[L];
                        to_leader[true_idx][c]=tmp1[L];
                    }
                    for(auto&to:g[u]){
                        if(to==p)continue;
                        if(!alive[to])continue;
                        dfs1(dfs1,to,u);
                    }
                    ds.rollback();
                    return;
                };
                if(i!=-1)dfs1(dfs1,x,c);
                else true_idx=group[c],L=leader[true_idx],dfs2(dfs2,c,-1,0,0);
            };
            for(auto&i:leader_idx){
                push(g[c][i],i);
            }
            if(leader[group[c]]==c)push(c,-1);

            alive[c]=0;
            for(auto&to:g[c])if(alive[to])decomposition(decomposition,to);
        };
        decomposition(decomposition,0);
    }
    auto merge_sorted=[&](vc<int>&a,vc<int>&b){
        ll inv=0;
        int nb=0;
        for(auto&x:a){
            while(nb!=b.size()&&b[nb]<x)nb++;
            inv+=nb;
        }
        return inv;
    };
    auto merge_sorted2=[&](vc<int>&a,vc<int>&b,vc<int>&c){
        ll inv=0;
        int nb=0;
        int nc=0;
        for(auto&x:a){
            if(nc!=c.size()&&x==c[nc]){
                nc++;
                continue;
            }
            while(nb!=b.size()&&b[nb]<x)nb++;
            inv+=nb;
        }
        return inv;
    };
    auto merge_sorted3=[&](vc<int>&a,vc<int>&b,vc<int>&c){
        ll inv=0;
        int nb=0;
        int nc=0;
        int off=0;
        for(auto&x:a){
            while(nb!=b.size()&&b[nb]<x){
                if(nc!=c.size()&&b[nb]==c[nc]){
                    nc++;
                    off++;
                    continue;
                }
                nb++;
            }
            inv+=nb-off;
        }
        return inv;
    };
    ll ans;
    auto dist=[&](int a,int b){
        return tree.depth(a)+tree.depth(b)-tree.depth(tree.lca(a,b))*2;
    };
    vc<ll>res;
    
    ll off=0;
    rep(i,Q.size()){
        if(lock){
            Q[i].first+=off,Q[i].second+=off;
            Q[i].first%=n,Q[i].second%=n;
        }
        Q[i].first--,Q[i].second--;
        if(Q[i].first<0)Q[i].first+=n;
        if(Q[i].second<0)Q[i].second+=n;
        auto get=[&](int a,int b){
            if(leader[group[a]]==a){
                return from_leader[group[a]][b];
            }
            if(leader[group[b]]==b){
                return to_leader[group[b]][a];
            }
            assert(0);
        };
        auto sol=[&](int a,int b)->ll{
            if(leader[group[a]]==a||leader[group[b]]==b){
                return get(a,b);
            }
            if(group[a]==group[b]){
                if(bel_sub[a]==bel_sub[b]){
                    return inv_sub[bel_sub[a]][sub_id[a]][sub_id[b]];
                }else{
                return get(a,leader[group[a]])+get(leader[group[a]],b)+merge_sorted(sorted_seq[a],sorted_seq[b]);
                }
            }
            int L=tree.lca(a,b);
            if(L==a){
                int L1=tree.nxt(L,leader[group[a]]);
                auto t1=sorted_seq[L1];
                insert(t1,A[leader[group[a]]]);
                return
                +get(leader[group[a]],b)
                -get(leader[group[a]],leader[group[b]])
                -merge_sorted(t1,sorted_seq[b])
                +get(a,leader[group[b]]);
            }
            if(L==b){
                int L1=tree.nxt(b,leader[group[b]]);
                auto t1=sorted_seq[L1];
                insert(t1,A[leader[group[b]]]);
                return
                +get(a,leader[group[b]])
                -get(leader[group[a]],leader[group[b]])
                -merge_sorted(sorted_seq[a],t1)
                +get(leader[group[a]],b);
            }
            auto bet=[&](int a,int b,int c){
                return dist(a,c)+dist(c,b)==dist(a,b);
            };
            if(!bet(a,b,leader[group[a]])){
                int L2=tree.nxt(L,leader[group[a]]);
                auto t1=sorted_seq[L2];
                insert(t1,A[leader[group[a]]]);
                return
                +get(a,leader[group[b]])
                +get(leader[group[a]],b)
                -merge_sorted(t1,sorted_seq[b])
                -get(leader[group[a]],leader[group[b]])
                +merge_sorted2(sorted_seq[a],sorted_seq[b],sorted_seq[L]);
            }
            if(!bet(a,b,leader[group[b]])){
                int L2=tree.nxt(L,leader[group[b]]);
                auto t1=sorted_seq[L2];
                insert(t1,A[leader[group[b]]]);
                return
                +get(a,leader[group[b]])
                +get(leader[group[a]],b)
                -merge_sorted(sorted_seq[a],t1)
                -get(leader[group[a]],leader[group[b]])
                +merge_sorted3(sorted_seq[a],sorted_seq[b],sorted_seq[L]);
            }
            return get(a,leader[group[b]])+get(leader[group[a]],b)-get(leader[group[a]],leader[group[b]])+merge_sorted(sorted_seq[a],sorted_seq[b]);
        };
            off=sol(Q[i].first,Q[i].second);
            res.push_back(off);
        }
        return res;
}   
void sol(){
    int n;
    cin>>n;
    vc<pair<int,int>>e(n-1);
    rep(i,n-1){
        cin>>e[i].first>>e[i].second;
    }
    vc<int>A(n);
    rep(i,n)cin>>A[i];
    int Q;
    cin>>Q;
    vc<pair<int,int>>Query(Q);
    rep(i,Q){
        cin>>Query[i].first>>Query[i].second;
    }
    auto res=solve(n,e,A,Query);
    for(auto&x:res)cout<<x<<endl;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    sol();
}