#include using namespace std; #include using namespace atcoder; // #include // using namespace boost::multiprecision; #define ll long long #define ld long double #define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define vi vector #define vl vector #define vd vector #define vb vector #define vs vector #define vc vector #define ull unsigned long long #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() template inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; } // #define ll int // #define ll int128_t // #define ll int256_t // #define ll cpp_int constexpr ll inf = (1ll << 60); // constexpr ll inf = (1 << 30); // const double PI=3.1415926535897932384626433832795028841971; // ll rui(ll a,ll b){ // if(b==0)return 1; // if(b%2==1) return a*rui(a*a,b/2); // return rui(a*a,b/2); // } // vl fact; // ll kai(ll n){ // fact.resize(n,1); // rep(i,n-1)fact[i+1]=fact[i]*(i+1); // } // using mint = ld; using mint = modint998244353;//static_modint<998244353> // using mint = modint1000000007;//static_modint<1000000007> // using mint = static_modint<922267487>; // 多分落とされにくい NOT ntt-friendly // using mint = static_modint<469762049>; // ntt-friendly // using mint = static_modint<167772161>; // ntt-friendly // using mint = modint;//mint::set_mod(mod); // ll const mod=1000000007ll; // ll const mod=998244353ll; // ll modrui(ll a,ll b,ll mod){ // a%=mod; // if(b==0)return 1; // if(b%2==1) return a*modrui(a*a%mod,b/2,mod)%mod; // return modrui(a*a%mod,b/2,mod)%mod; // } // ll inv(ll x){ // x%=mod; // return modrui(x,mod-2); // } // void incr(vl &v,ll n){// n進法 // ll k=v.size(); // v[k-1]++; // ll now=k-1; // while (v[now]>=n) // { // v[now]=0; // if(now==0)break; // v[now-1]++; // now--; // } // return; // } // vector fact,invf; // void init_modfact(ll sz){ // fact.resize(sz); // invf.resize(sz); // fact[0]=1; // rep(i,sz-1){ // fact[i+1]=fact[i]*(i+1); // } // invf[sz-1]=1/fact[sz-1]; // for(ll i=sz-2; i>=0; i--){ // invf[i]=invf[i+1]*(i+1); // } // } // mint choose(ll n,ll r){ // if(n modpow,invpow; // void init_modpow(ll x,ll sz){ // mint inv=1/mint(x); // modpow.assign(sz,1); // invpow.assign(sz,1); // rep(i,sz-1){ // modpow[i+1]=modpow[i]*x; // invpow[i+1]=invpow[i]*inv; // } // } // long long phi(long long n) {// O(sqrt(n)) // long long res = n; // for (long long i = 2; i * i <= n; i++) { // if (n % i == 0) { // res -= res / i; // while (n % i == 0) n /= i; // } // } // if (n > 1) res -= res / n; // return res; // } /**https://judge.yosupo.jp/submission/364486 * https://judge.yosupo.jp/submission/364492 * HLD_Lazy (Heavy-Light Decomposition + lazy_segtree) * * 【概要】 * 木上のパス・部分木に対する区間更新と区間取得を O(log^2 N) や O(log N) で処理する。 * atcoder::lazy_segtree を内部で完全隠蔽しているため、ACLと同じオラクルを書くだけで使える。 * パスに関する操作は両端を含む * * 【特徴】 * - 頂点属性 (is_vertex = true) と辺属性 (is_vertex = false) の両方に自動対応。 * - 非可換な演算(行列や文字列など、順序が重要なもの)に完全対応(toggle関数で反転)。 * * 【できること(クエリ関数)】 * - prod_path(u, v) : u から v へのパスの総和(非可換の場合は u -> v の順序を守る) * - apply_path(u, v, f) : u から v へのパス上の全要素に f を作用させる * - prod_subtree(u) : u を根とする部分木内の総和 * - apply_subtree(u, f) : u を根とする部分木内の全要素に f を作用させる * - prod_outside(u) : u を根とする部分木「以外」の総和 * - apply_outside(u, f) : u を根とする部分木「以外」の全要素に f を作用させる * - lca(u, v) : u と v の最小共通祖先を取得 * * 【使用例】 * HLD_Lazy tree(N); * for(int i=0; i struct HLD_Lazy { int n; std::vector> g; std::vector> edges; std::vector sz, in, out, head, rev, parent, depth; int timer; bool is_vertex; atcoder::lazy_segtree seg; HLD_Lazy(int n) : n(n), g(n), sz(n, 1), in(n), out(n), head(n), rev(n), parent(n, -1), depth(n, 0), timer(0) {} // 1. 辺の追加 (0-indexed) // 辺属性の初期化に備えて、追加された順番(edges)を記憶しておく void add_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); edges.emplace_back(u, v); } // 2-A. 頂点に値を持つ場合の構築 void build_vertex(int root, const std::vector& init_S_vector) { assert((int)init_S_vector.size() == n); is_vertex = true; build_dfs(root); std::vector seg_init(n, e()); // HLDの行きがけ順(in)に従って初期配列を並べ替え for (int i = 0; i < n; i++) seg_init[in[i]] = init_S_vector[i]; seg = atcoder::lazy_segtree(seg_init); } // 2-B. 辺に値を持つ場合の構築 void build_edge(int root, const std::vector& init_S_edges) { assert((int)init_S_edges.size() == n - 1); is_vertex = false; build_dfs(root); std::vector seg_init(n, e()); // 各辺を「深い方の頂点(child)」に紐づけてセグ木に載せる for (int i = 0; i < n - 1; i++) { int u = edges[i].first; int v = edges[i].second; int child = depth[u] > depth[v] ? u : v; seg_init[in[child]] = init_S_edges[i]; } seg = atcoder::lazy_segtree(seg_init); } // --- クエリ関数群 --- // パス上の取得 (u から v への順序を考慮して取得) S prod_path(int u, int v) { S L = e(), R = e(); // Lはuから登る側、Rはvから登る(=LCAからvへ降りる)側 while (head[u] != head[v]) { if (depth[head[u]] > depth[head[v]]) { // u側を登る場合は、下から上への逆走になるので rev_op で反転させる L = op(L, rev_op(seg.prod(in[head[u]], in[u] + 1))); u = parent[head[u]]; } else { // v側を登る場合は、全体として見ればLCAから降りる方向なのでそのまま結合 R = op(seg.prod(in[head[v]], in[v] + 1), R); v = parent[head[v]]; } } // 最後に同じHeavy Path上で合流した部分の処理 if (depth[u] > depth[v]) { // u側からvへ登る (逆走) L = op(L, rev_op(seg.prod(in[v] + !is_vertex, in[u] + 1))); } else { // u(LCA)からvへ降りる (順走) R = op(seg.prod(in[u] + !is_vertex, in[v] + 1), R); } return op(L, R); // 最後に登り(L)と降り(R)を結合 } // パス上の更新 void apply_path(int u, int v, const F& f) { // applyは順序に依存しないため、単純に区間ごとに f を投げるだけでよい while (head[u] != head[v]) { if (depth[head[u]] > depth[head[v]]) { seg.apply(in[head[u]], in[u] + 1, f); u = parent[head[u]]; } else { seg.apply(in[head[v]], in[v] + 1, f); v = parent[head[v]]; } } if (depth[u] > depth[v]) { seg.apply(in[v] + !is_vertex, in[u] + 1, f); } else { seg.apply(in[u] + !is_vertex, in[v] + 1, f); } } // 部分木の取得 S prod_subtree(int u) { // !is_vertex(辺属性)の場合は、部分木の根である u 自身に紐づく辺を含めない return seg.prod(in[u] + !is_vertex, out[u]); } // 部分木の更新 void apply_subtree(int u, const F& f) { seg.apply(in[u] + !is_vertex, out[u], f); } // 部分木外の取得 S prod_outside(int u) { S res = e(); int l = in[u] + !is_vertex; // 部分木 [in[u], out[u]) の「左側」と「右側」をそれぞれ取得して結合 if (l > 0) res = op(res, seg.prod(0, l)); if (out[u] < n) res = op(res, seg.prod(out[u], n)); return res; } // 部分木外の更新 void apply_outside(int u, const F& f) { int l = in[u] + !is_vertex; if (l > 0) seg.apply(0, l, f); if (out[u] < n) seg.apply(out[u], n, f); } // 最小共通祖先 int lca(int u, int v) { while (head[u] != head[v]) { if (depth[head[u]] < depth[head[v]]) std::swap(u, v); u = parent[head[u]]; } return depth[u] < depth[v] ? u : v; } private: void build_dfs(int root) { timer = 0; dfs_sz(root, -1, 0); head[root] = root; dfs_hld(root, -1); } // 各部分木のサイズ(sz)と深さ(depth)を計算し、最も重い子(Heavy Child)を決定する void dfs_sz(int v, int p, int d) { parent[v] = p; depth[v] = d; int max_sub = 0; for (int& u : g[v]) { if (u == p) continue; dfs_sz(u, v, d + 1); sz[v] += sz[u]; if (max_sub < sz[u]) { max_sub = sz[u]; // g[v][0] に常に Heavy Child が来るように swap std::swap(g[v][0], u); } } } // Heavy Child を優先してDFSし、行きがけ順(in)と帰りがけ順(out)を記録する void dfs_hld(int v, int p) { in[v] = timer++; rev[in[v]] = v; for (int u : g[v]) { if (u == p) continue; // Heavy Child なら親と同じパス(head)、Light Child なら新しいパスの始点 head[u] = (u == g[v][0] ? head[v] : u); dfs_hld(u, v); } out[v] = timer; // out[v] は部分木クエリ用の右端インデックス } }; struct S{ ll val,len; }; struct F{ ll add; }; S op(S l,S r){ return S{l.val+r.val,l.len+r.len}; } S e(){return S{0,0};} S mapping(F f,S s){ s.val+=s.len*f.add; return s; } F comp(F f,F g){return F{f.add+g.add};} F id(){return F{0};} S rev_op(S s){return s;} void solve(){ ll n; cin >> n; HLD_Lazy hld(n); vector inits(n,S{0,1}); rep(i,n-1){ ll u,v; cin >> u >> v; u--; v--; hld.add_edge(u,v); } hld.build_vertex(0,inits); ll q; cin >> q; ll ans=0; while(q--){ ll a,b; cin >> a >> b; a--; b--; hld.apply_path(a,b,F{1}); ans+=hld.prod_path(a,b).val; } cout << ans << endl; } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); ll t = 1; // cin >> t; while (t--) solve(); }