#include #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define ll long long #define ALL(a) (a).begin(),(a).end() #define rep(i,n) for(int i=0;i<(n);i++) #define rrep(i,n) for(int i=n-1;i>=0;i--) #define fi first #define se second #define pb push_back #define Pii pair #define Pll pair #define fout(num) cout << fixed << setprecision(20) << (num) << endl template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a> dp(n,vector(n)) //2-dim:vector> vv(n, vector(m, d)); //3-dim:vector>> vvv(n, vector>(m, vector(l, d))); using namespace std; template struct BIT { vector dat[2]; Abel UNITY_SUM = 0; // to be set /* [1, n] */ BIT(int n) { init(n); } void init(int n) { for (int iter = 0; iter < 2; ++iter) dat[iter].assign(n + 1, UNITY_SUM); } /* a is 1-indexed */ inline void sub_add(int p, int a, Abel x) { for (int i = a; i < (int)dat[p].size(); i += i & -i) dat[p][i] = dat[p][i] + x; } inline void add(int a, int b, Abel x) { sub_add(0, a, x * -(a - 1)); sub_add(1, a, x); sub_add(0, b, x * (b - 1)); sub_add(1, b, x * (-1)); } /* [1, a], a is 1-indexed */ inline Abel sub_sum(int p, int a) { Abel res = UNITY_SUM; for (int i = a; i > 0; i -= i & -i) res = res + dat[p][i]; return res; } inline Abel sum(int a, int b) { return sub_sum(0, b - 1) + sub_sum(1, b - 1) * (b - 1) - sub_sum(0, a - 1) - sub_sum(1, a - 1) * (a - 1); } /* debug */ void print() { for (int i = 1; i < (int)dat[0].size(); ++i) cout << sum(i, i + 1) << ","; cout << endl; } }; struct HL_decomposition{ private: int n; vector> G; vector sz, par; // 部分木のサイズ,親頂点 vector root; // 頂点が属するHeavy集合で,最も根に近い頂点 vector in, out; // 頂点のEuler Tour上での始点/終点 // 部分木のサイズを取得し,0番目の子へのパスがHeavyにする void dfs_size(int v, int pre){ sz[v] = 1; par[v] = pre; for(auto &u:G[v]){ if(u == pre) continue; dfs_size(u, v); sz[v] += sz[u]; if(sz[u] > sz[G[v][0]]){ swap(u, G[v][0]); } } } // パスを構築 void dfs_path(int v, int pre, int &num){ in[v] = num; num++; for(auto u:G[v]){ if(u == pre) continue; root[u] = (u==G[v][0] ? root[v] : u); dfs_path(u, v, num); } out[v] = num; } public: // 初期化 HL_decomposition(vector> _G){ G = _G; n = (int)G.size(); sz.resize(n); par.assign(n, -1); in.assign(n, -1); out.assign(n, -1); root.assign(n, -1); dfs_size(0, -1); root[0] = 0; int tmp = 0; dfs_path(0, -1, tmp); } inline int get_inpos(int v){ return in[v]; } inline int get_outpos(int v){ return out[v]; } inline int get_subtree_size(int v){ return sz[v]; } // 最近共通祖先を求める.圧縮後の高さは高々log(n)なので,同じ所に入るまで愚直に見ればよい. int lca(int u, int v){ int ru = root[u], rv = root[v]; while(root[u]!=root[v]){ if(in[ru] > in[rv]){ u = par[u]; ru = root[u]; }else{ v = par[v]; rv = root[v]; } } if(in[u]>in[v]) return v; else return u; } // クエリ処理を行う.事前にサイズnのセグ木などを宣言する. // 部分木に対するクエリ処理.例:hl.query(v, [&](int l, int r){seg.update(l, r, x);}) void query_subtree(int v, const function &func){ func(in[v], out[v]); } // パスに対するクエリ処理.例:hl.query(v, [&](int l, int r){ans+=seg.query(l,r);}) void query_path(int u, int v, const function &func){ int ru = root[u], rv = root[v]; while(root[u]!=root[v]){ if(in[u] > in[v]){ func(in[ru], in[u]+1); u = par[u]; ru = root[u]; }else{ func(in[rv], in[v]+1); v = par[v]; rv = root[v]; } } if(in[u]>in[v]) swap(u, v); func(in[u], in[v]+1); } void query_nodes_path(int u, int v, const function &func){ while (true) { if (in[u] > in[v]) swap(u, v); func(max(in[root[v]], in[u]), in[v]); if (root[u] != root[v]) v = par[root[v]]; else break; } } }; void solve() { int n; cin>>n; vector> G(n); rep(i,n-1){ int u,v; cin>>u>>v; u--; v--; G[u].pb(v); G[v].pb(u); } HL_decomposition hld(G); BIT bit(n+1); ll res = 0; int Q;cin>>Q; while(Q--){ int a,b; cin>>a>>b; a--; b--; hld.query_nodes_path(a,b,[&](int l,int r){ bit.add(l+1, r+2, 1); res += bit.sum(l+1, r+2);}); } cout<