結果
| 問題 | No.3194 Do Optimize Your Solution |
| コンテスト | |
| ユーザー |
 sumsumf
|
| 提出日時 | 2025-12-20 22:15:27 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 27,672 bytes |
| 記録 | |
| コンパイル時間 | 6,251 ms |
| コンパイル使用メモリ | 282,856 KB |
| 実行使用メモリ | 335,200 KB |
| 最終ジャッジ日時 | 2025-12-20 22:16:13 |
| 合計ジャッジ時間 | 43,852 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 2 |
| other | RE * 12 TLE * 5 |
ソースコード
# 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();
}