#include using namespace std; using ll = long long; using P = pair; /* ☆HLDの使い方☆ まずbuildする ①頂点に値がある場合: - 代入はseg[hld.in[v]] = a[v] - パスクエリはfor_each_vertex(u,v) - 部分木クエリは hld.in[v] ~ hld.out[v]で ②辺に値がある場合: - 代入(aとbの間の辺に重みw)は (par[a] == b ? seg[hld.in[a]] = w : seg[hld.in[b]] = w) - パスクエリはfor_each_edge(u, v) 非可換だと壊れると思う */ struct HLD { int n; vector par,in,out,head,inv,sub; vector> g; HLD(){}; HLD(int n) { g = vector>(n); sub = par = in = out = head = inv = vector(n); } void add_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } int dfs_hld(int c, int p) { sub[c] = 1; if(p != -1) g[c].erase(find(g[c].begin(), g[c].end(), p)); for(auto &d :g[c]) { par[d] = c; sub[c] += dfs_hld(d, c); if(sub[d] > sub[g[c][0]]) swap(d, g[c][0]); } return sub[c]; } void dfs2(int c, int &i) { in[c] = i++; inv[in[c]] = c; for(auto &d : g[c]) { head[d] = (g[c][0] == d ? head[c] : d); dfs2(d,i); } out[c] = i; } void build(int r=0) { dfs_hld(0,-1); int cnt = 0; dfs2(0,cnt); } int lca(int u, int v) { while(1) { if(in[u] > in[v]) swap(u,v); if(head[u] == head[v]) return u; v = par[head[v]]; } } vector> for_each_vertex(int u, int v) { //seg[in[u]] に代入 vector> path; while(1) { if(in[u] > in[v]) swap(u,v); if(head[u] != head[v]) { path.push_back({in[head[v]], in[v] + 1}); v = par[head[v]]; }else { path.push_back({in[u],in[v]+1}); return path; } } } vector> for_each_edge(int u, int v) { //子に辺の情報を代入 vector

path; while(1) { if(in[u] > in[v]) swap(u,v); if(head[u] != head[v]) { path.push_back({in[head[v]], in[v] + 1}); v = par[head[v]]; } else { path.push_back({in[u] + 1, in[v] + 1}); return path; } } } }; template struct fenwick_tree { int n; vector bit; fenwick_tree(){}; fenwick_tree(int n):n(n), bit(n+1,0){} void add(int i, T x) { i++; for(int idx=i; idx<=n; idx += (idx & (-idx))) bit[idx] += x; } T sum(int i) { T s(0); for(int idx=i; idx>0; idx-= (idx & (-idx)) ) s += bit[idx]; return s; } T sum(int l, int r) {return sum(r) - sum(l);} int lower_bound(T w) { if(w <= 0) return 0; int x=0, r=1; while(r < n) r = r<<1; for(int len = r; len > 0; len = len>>1) { if(x + len < n && bit[x+len] < w) { w -= bit[x + len]; x += len; } } return x+1; } }; #include using namespace atcoder; /* ☆atcoder::lazy_segtreeの使い方☆ lazy_segtree 作用素の合成composition(F f, F g) は f∘gとなる(つまりfが後から来たもの) ↓↓↓↓↓↓区間和・区間加算 */ struct S { ll x; int l; }; S op(S a, S b){return {a.x + b.x, a.l + b.l};} S e(){return {0,0};} using F = ll; S mapping(F f, S x) {return {x.x + x.l*f,x.l};} F composition(F f, F g){return f + g;} F id(){return 0;} int main() { int N; cin>>N; HLD hl(N); for(int i=0; i>u>>v; u--,v--; hl.add_edge(u,v); } hl.build(); lazy_segtree seg(N); for(int i=0; i>Q; ll ans = 0; while(Q--) { int u,v;cin>>u>>v; u--,v--; auto s = hl.for_each_vertex(u,v); for(auto [l,r]:s) { ans += seg.prod(l,r).x + (r - l); seg.apply(l,r,1); } } cout << ans << endl; }