#include #include using namespace std; using namespace atcoder; istream &operator>>(istream &is, modint &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); } istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); } istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); } typedef long long ll; typedef vector> Graph; typedef pair pii; typedef pair pll; #define rep(i,n) for (int i = 0;i < (int)(n); i++) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define my_sort(x) sort(x.begin(), x.end()) #define my_max(x) *max_element(all(x)) #define my_min(x) *min_element(all(x)) template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const int INF = (1<<30) - 1; const ll LINF = (1LL<<62) - 1; const int MOD = 998244353; const int MOD2 = 1e9+7; const double PI = acos(-1); vector di = {1,0,-1,0}; vector dj = {0,1,0,-1}; template void print_2dvector(vector> &vec){ int H = vec.size(); for(int i=0;i void print_vector(vector &vec){ int N = vec.size(); cout << '['; for(int i=0;i # define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define debug(...) (static_cast(0)) #endif class heavy_light_decomposition { const int n; vector> g; vector in, out, size, head, par; int it; void erase_par(int v, int prev) { par[v] = prev; for (auto& u : g[v]) { if (u == g[v].back()) break; if (u == prev) swap(u, g[v].back()); erase_par(u, v); } g[v].pop_back(); } void dfs1(int v) { for (auto& u : g[v]) { dfs1(u); size[v] += size[u]; if (size[u] > size[g[v][0]]) swap(u, g[v][0]); } } void dfs2(int v) { in[v] = it++; for (auto u : g[v]) { head[u] = (u == g[v][0] ? head[v] : u); dfs2(u); } out[v] = it; } public: heavy_light_decomposition(int n_) : n(n_), g(n), in(n, -1), out(n, -1), size(n, 1), head(n), par(n, -1), it(0) {} heavy_light_decomposition(const vector>& G) : n(G.size()), g(G), in(n, -1), out(n, -1), size(n, 1), head(n), par(n, -1), it(0) {} void add_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } void build(int rt = 0) { for (auto v : g[rt]) erase_par(v, rt); dfs1(rt); head[rt] = rt; dfs2(rt); } int get_id(int v) { return in[v]; } int get_lca(int u, int v) { while (true) { if (in[u] > in[v]) swap(u, v); if (head[u] == head[v]) return u; v = par[head[v]]; } } void path_query(int u, int v, function f) { while (true) { if (in[u] > in[v]) swap(u, v); f(max(in[head[v]], in[u]), in[v] + 1); if (head[u] == head[v]) return; v = par[head[v]]; } } void subtree_query(int v, function f) { f(in[v], out[v]); } }; // https://kazuma8128.hatenablog.com/entry/2018/07/16/010500 struct S{ long long value; int size; }; using F = long long; S op(S a, S b){ return {a.value+b.value, a.size+b.size}; } S e(){ return {0, 0}; } S mapping(F f, S x){ return {x.value + f*x.size, x.size}; } F composition(F f, F g){ return f+g; } F id(){ return 0; } // https://atcoder.jp/contests/abc138/submissions/38777632 int main(){ cin.tie(0); ios_base::sync_with_stdio(false); int N; cin >> N; Graph g(N); lazy_segtree seg(N); rep(i,N) seg.set(i,S{0,1}); rep(i,N-1){ int a,b; cin >> a >> b; a--; b--; g[a].push_back(b); g[b].push_back(a); } heavy_light_decomposition hld(g); hld.build(); ll ans = 0ll; int Q; cin >> Q; while(Q--){ int a,b; cin >> a >> b; a--; b--; hld.path_query(a,b,[&](int l, int r){ans += seg.prod(l,r).value + seg.prod(l,r).size;}); hld.path_query(a,b,[&](int l, int r){seg.apply(l,r,1);}); debug(ans,Q); for(int i=0;i