#include using namespace std; using ll = long long; using ull = unsigned long long; using PT = priority_queue, vector>, greater>>; using PPQ = priority_queue, vector>, greater>>; using PQ = priority_queue, greater>; using P = pair; using vvvvl = vector>>>; using vvvi = vector>>; using vvvl = vector>>; using vvvc = vector>>; using vvvd = vector>>; using vvi = vector>; using vvl = vector>; using vvs = vector>; using vvc = vector>; using vvp = vector>>; using vvb = vector>; using vvd = vector>; using vp = vector>; using vi = vector; using vl = vector; using vs = vector; using vc = vector; using vb = vector; using vd = vector; #define vvvm = vector>> #define vvm = vector> #define vm = vector #define umap = unordered_map #define uset = unordered_set #define rrr(l, r) mt()%(r-l+1)+l #define rep(i, s, f) for(ll i = s; i <= f; i++) #define per(i, s, f) for(ll i = s; i >= f; i--) #define all0(x) (x).begin() ,(x).end() #define all(x) (x).begin() + 1, (x).end() #define ENDL '\n' //////////////////////////////////////////////////////////////////////////////////////////////////////////// //これが本当の組み込み関数ってね(笑) template T or_less(vector &A, T x) { //x以下で最大要素の添字 前提: sort済み 存在しない: -1 return distance(A.begin(), upper_bound(A.begin(), A.end(), x)-1); } template T under(vector &A, T x) { //x未満の最大要素の添字 前提: sort済み 存在しない: -1 return distance(A.begin(), lower_bound(A.begin(), A.end(), x)-1); } template T or_more(vector &A, T x) { //x以上で最小要素の添字  前提: sort済み 存在しない: N . //distanceのA.beginは添字を出すために常にA.begin() NG: A.begin() + 1 return distance(A.begin(), lower_bound(A.begin(), A.end(), x)); } template T over(vector &A, T x) { //xより大きい最小要素の添字前提: sort済み 存在しない: N return distance(A.begin(), upper_bound(A.begin(), A.end(), x)); } template vector vec_shift(vector A, ll step, ll dir = 1, ll indexed = 1) {//dir = 1 : 右シフト dir = -1 : 左シフト ll N = A.size() - indexed; vector res(N+1); rep(i, indexed, N) { ll idx = i - step * dir; if(idx < indexed) idx += N; if(idx > N) idx -= N; res.at(i) = A.at(idx); } return res; } template void UNIQUE(vector &A) { sort(all0(A)); return A.erase(unique(A.begin(), A.end()), A.end()); } template void rev90(vector> &A, int indexed = 1) { reverse(A.begin() + indexed, A.end()); int n = A.size(); rep(i, indexed, n-1) { rep(j, i+1, n-1) { swap(A.at(i).at(j), A.at(j).at(i)); } } } int msb(long long a) { if(a == 0) return -1; return 64 - int(__builtin_clzll(a)); } void chmin(ll &a, ll b) { a = min(a, b); } void chmax(ll &a, ll b) { a = max(a, b); } ////////////////////////////////////////////////////////////////////// //数学系 /////////////////////////////////////////////////////////////////////// ll round(ll x, ll i) {return ll(x + 5 * pow(10, i-1))/ll(pow(10, i)) * ll(pow(10, i));} vp insu_bunkai(ll N) { vp res; for (ll i = 2; i * i <= N; i++) { ll cnt = 0; while(N % i == 0) { cnt++; N /= i; } if(cnt != 0) res.push_back(P(i, cnt)); } if(N != 1) res.push_back(P(N, 1)); return res; } ll extgcd (ll a, ll b, ll &x, ll &y) { if(b == 0) { x = 1;y = 0;return a;} ll d = extgcd(b, a%b, y, x); y -= a/b * x; return d; } template T ceil(T a, T b) { assert(b != 0); if(a % b == 0) return a / b; if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b + 1; else return a / b; } template T floor(T a, T b) { assert(b != 0); if(a % b == 0) return a / b; if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b; else return a/b - 1; } ll modpow(ll x, ll y, ll mod) { if(x > mod) x %= mod; if(y == 0) return 1; ll res = modpow(x, y >> 1, mod); res = res * res % mod; if(y & 1) res *= x, res %= mod; return res; } ll sqrt_(ll a) { ll l = 0; ll r = 3037000499LL; while(l < r) { ll mid = (l + r + 1) / 2; if(mid * mid <= a) l = mid; else r = mid - 1; } return l; } ////////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //グローバル変数を置くところ(情報工学意識高め) //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") const ll int_max = 1001001001; const ll ll_max = 1001001001001001001LL; const double pi = 3.141592653589793; vl dx{0, 1, 0, -1, 0, 1, 1, -1, -1}; // (番兵) → ↓ ← ↑ ※ 右から時計回り 注 : グリッド or 座標で上下は反転する。 vl dy{0, 0, -1, 0, 1, 1, -1, -1, 1}; //const ll mod = 1000000007; //const ll mod = 998244353; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// template struct LazySegTree { using FX = function;//全て右側を左側に作用させる。 : Xを融合させる using FA = function;//Xに作用素Mを作用させる using FM = function;//作用素を合成する using FL = function;//作用素の影響が長さに関係のある場合 int n; FX fx; FA fa; FM fm; FL fl; const X ex;//単位元 const M em;//単位元 vector dat; vector lazy; LazySegTree(int siz, FX _fx, FA _fa, FM _fm, FL _fl, X _ex, M _em) : fx(_fx), fa(_fa), fm(_fm), fl(_fl), ex(_ex), em(_em) { n = 1; while(n < siz) n <<= 1; dat.assign(n * 2, ex); lazy.assign(n * 2, em); } void set(int i, X x) { dat.at(i + n - 1) = x; } void init() { per(i, n-1, 1) { dat.at(i) = fx(dat.at(i*2), dat.at(i * 2 + 1)); } } void eval(int k, int len) { if(lazy[k] == em) return; if(k < n) { lazy[k * 2] = fm(lazy[k * 2], lazy[k]); lazy[k * 2 + 1] = fm(lazy[k * 2 + 1], lazy[k]); } dat[k] = fa(dat[k], fl(lazy[k], len)); lazy[k] = em; } void update(int a, int b, M m, int l, int r, int k) { eval(k, r-l); if(r <= a || b <= l) return; if(a <= l && r <= b) { lazy[k] = fm(lazy[k], m); eval(k, r-l); } else { int mid = (l + r)/2; update(a, b, m, l, mid, k * 2); update(a, b, m, mid, r, k * 2 + 1); dat[k] = fx(dat[k * 2], dat[k * 2 + 1]); } } X query(int a, int b, int l, int r, int k) { eval(k,r-l); if(r <= a || b <= l) return ex; if(a <= l && r <= b) return dat[k]; ll mid = (l + r)/2; X L = query(a, b, l, mid, k * 2); X R = query(a, b, mid, r, k * 2 + 1); return fx(L, R); } void change(int l, int r, M m) { update(l, r + 1, m, 1, n + 1, 1); } X get(int l, int r) { return query(l, r + 1, 1, n + 1, 1); } }; //int siz, FX _fx, FA _fa, FM _fm, FL _fl, X _ex, M _em using XX = ll; XX ex = 0; using MM = ll; MM em = 0; XX fx(const XX& a, const XX& b) { return a+b; } MM fm(const MM& a, const MM& b) { return a+b; } XX fa(const XX& a, const MM& b) { return a + b; } MM fl(const MM& a, const int& l) { return a * l; } LazySegTree seg(100000, fx, fa, fm, fl, ex, em); template struct HL { vector siz;//[元の頂点番号] = サイズ vector num;//[元の頂点番号] = 振り直した頂点番号 vector numrev; vector par;//[振られた] = 振られた 自分の親 vector head;//[振られた番号] = 振られた番号 自分の連結成分の頭 int N; vector dat;//セグ木用の配列 int size = 1; HL(int _N, vvl& G): N(_N) { par.resize(N+1); iota(par.begin(), par.end(), 0); siz.resize(N+1, 1); num.assign(N+1, -1); numrev.resize(N+1, -1); head.resize(N+1); while(size < N) size <<= 1; dat.assign(size*2, ex); auto dfs_siz = [&](auto dfs_siz, int now, int prev) -> void { int sum = 1; for(int to : G[now]) { if(to == prev) continue; dfs_siz(dfs_siz, to, now); sum += siz[to]; } siz[now] = sum; return; }; dfs_siz(dfs_siz, 1, -1); rep(i, 1, N){ sort(G[i].begin(), G[i].end(), [&](int a, int b) { return siz[a] > siz[b]; }); } int idx = 1; auto dfs_bunkai = [&](auto dfs_bunkai, int now, int prev, int hed) -> void { num[now] = idx;//番号付 numrev[idx] = now; idx++; par[num[now]] = prev;//親の頂点 //1だけは直前も自分も1 if(hed == -1)hed = num[now]; head[num[now]] = hed; bool flag = true; rep(i, 0, int(G[now].size()) - 1) { if(num[G[now][i]] != -1) continue; if(flag) dfs_bunkai(dfs_bunkai, G[now][i], num[now], hed), flag = false; else dfs_bunkai(dfs_bunkai, G[now][i], num[now], -1); } return; }; dfs_bunkai(dfs_bunkai, 1, 1, -1); } // 振り終わった ////////////////////////////////////////// X get(int u, int v) {// 入 : 元番号 int w = num[getLCA(u, v)];//lcaで左右に分ける u = num[u]; v = num[v]; X L = ex, R = ex; while(u != w) { int hed = max(head[u], w+1); seg.change(hed, u, 1); L = fx(seg.get(hed, u), L); //交換則を意識してない 意識するならqueryから変えなきゃいけない(あるいは、配列を分けるか?) if(hed != w) u = par[hed]; else u = w; } seg.change(w, w, 1); L = fx(seg.get(w, w), L);//根から上の方へ while(v != w) { int hed = max(head[v], w+1); seg.change(hed, v, 1); R = fx(seg.get(hed, v), R); //根から上の方へ if(hed != w) v = par[hed]; else v = w; } //R = operation(query(1, size+1, w, w+1, 1), R); これをしてないので、RはまだLCAに辿り着いてない。 return fx(L, R);//交換則を要する時はこの行を変更する必要があるかもしれない : 無いと思うが } int getLCA(int a, int b) {//入 : 元番号 出 : 元番号 a = num[a]; b = num[b]; while(true) { if(a > b) swap(a, b); if(head[a] == head[b]) return numrev[a]; b = par[head[b]]; } } int parent(int a) {//入 : 元番号 return numrev[par[num[a]]]; } }; void solve() { ll N; cin >> N; vvl G(N+1); rep(i,1,N-1){ ll u, v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } ll ans = 0; HL hld(N, G); ll Q; cin >> Q; rep(qi, 1, Q) { ll a, b; cin >> a >> b; ans += hld.get(a, b); } cout << ans << endl; } //尺取り法的な事をする時は、rは勿論"lもNを超え無いようにする"事!(違反するとエラーコード139が出たりする) //無断で0を平方数にカウントする人もいる //”部分文字列”と”連続部分文字列”は違うので確認すること //一般のグラフと、有向辺かつその貼り方に制約がある(多くの場合:番号がで解放に伸びる)はだいぶ違うので確認すること //座標を2で割った時の”切り捨て側(左側)”を求めるには 誤:(x / 2) マイナスの時!!! 正:floor(x, 2); //stringでの数字の下から1桁目は 正:S.at(N-1) 誤:S.at(0) //if(S.at(i) == 1) ← charなのに1...? // modは取りましたか...?(´・ω・`) //sortの比較関数は、 a == b ならば falseを返す必要がある(そうで無いとRE(発生しない場合もある)) int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(15); ll T = 1; //cin >> T; rep(i, 1, T) { solve(); } return 0; }