#include using namespace atcoder; using mint = modint; #include #define rep(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) #define repeq(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);i++) #define repreq(i,a,b) for(ll i=(ll)(a);i>=(ll)(b);i--) #define each(a,b) for(auto&(a):(b)) #define endl '\n' #define cYes cout<<"Yes"<()) #define pb push_back #define mp make_pair #define mt make_tuple #define tget(a,b) get(a) #define FI first #define SE second #define ALL(v) (v).begin(),(v).end() #define INFLL 3000000000000000000LL #define INF 1000000010 #define PI acos(-1.0L) using namespace std; typedef long long ll; typedef pair Pll; typedef tuple Tlll; typedef vector Vi; typedef vector VVi; typedef vector Vl; typedef vector VVl; typedef vector VVVl; typedef vector Vm; typedef vector VVm; typedef vector Vs; typedef vector Vd; typedef vector Vc; typedef vector Vb; typedef vector VPll; typedef priority_queue PQl; typedef priority_queue,greater> PQlr; /* print */ template ostream& operator<<(ostream& os,const vector &V){ int N=V.size();if(N==0){os< ostream& operator<<(ostream& os,const vector> &V){ int N=V.size();rep(i,0,N)os< ostream& operator<<(ostream&os,pairconst&P){os<void Vin(vector &v){int n=v.size();rep(i,0,n)cin>>v[i];} templateint SMALLER(vector &a,T x){ return lower_bound(a.begin(),a.end(),x)-a.begin();} templateint orSMALLER(vector &a,T x){ return upper_bound(a.begin(),a.end(),x)-a.begin();} templateint BIGGER(vector&a,T x){return a.size()-orSMALLER(a,x);} templateint orBIGGER(vector&a,T x){return a.size()-SMALLER(a,x);} templateint COUNT(vector &a,T x){ return upper_bound(ALL(a),x)-lower_bound(ALL(a),x);} templatebool chmax(T &a,T b) {if(abool chmin(T &a,T b) {if(a>b){a=b;return 1;}return 0;} templatevoid press(T &v){v.erase(unique(ALL(v)),v.end());} templatevector zip(vector b){pair p[b.size()+10]; int a=b.size();vector l(a);for(int i=0;ivector vis(vector &v){ vector S(v.size()+1);rep(i,1,S.size())S[i]+=v[i-1]+S[i-1];return S;} ll dem(ll a,ll b){return((a+b-1)/(b));} ll dtoll(double d,int g){return round(d*pow(10,g));} //const long long MOD = 1000000007; const long long MOD = 998244353; const double EPS = 1e-10; void init(){mint::set_mod(MOD); cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cout< > G; vector stsize, parent, pathtop, in, out; int root; void BuildStsize(int u, int p){ stsize[u] = 1, parent[u] = p; for(int& v : G[u]){ if(v == p){ if(v == G[u].back()) break; else swap(v, G[u].back()); } BuildStsize(v, u); stsize[u] += stsize[v]; if(stsize[v] > stsize[G[u][0]]){ swap(v, G[u][0]); } } } void BuildPath(int u, int p, int& tm){ in[u] = tm++; for(int v : G[u]){ if(v == p) continue; pathtop[v] = (v == G[u][0] ? pathtop[u] : v); BuildPath(v, u, tm); } out[u] = tm; } public: void add_edge(int u, int v){ G[u].push_back(v), G[v].push_back(u); } void build(int _root){ root = _root; int tm = 0; BuildStsize(root, -1); pathtop[root] = root; BuildPath(root, -1, tm); } //元の頂点のインデックスの配列上でのidを返す inline int get(int a){ return in[a]; } int lca(int a, int b){ int pa = pathtop[a], pb = pathtop[b]; while(pathtop[a] != pathtop[b]){ if(in[pa] > in[pb]){ a = parent[pa], pa = pathtop[a]; }else{ b = parent[pb], pb = pathtop[b]; } } if(in[a] > in[b]) swap(a, b); return a; } void subtree_query(int a, const function< void(int, int) > &func){ func(in[a], out[a]); } void path_query(int a, int b, const function< void(int, int) > &func){ int pa = pathtop[a], pb = pathtop[b]; while(pathtop[a] != pathtop[b]){ if(in[pa] > in[pb]){ func(in[pa], in[a] + 1); a = parent[pa], pa = pathtop[a]; }else{ func(in[pb], in[b] + 1); b = parent[pb], pb = pathtop[b]; } } if(in[a] > in[b]) swap(a, b); func(in[a], in[b] + 1); } HLdecomposition() {} HLdecomposition(int node_size) : V(node_size), G(V), stsize(V, 0), parent(V, -1), pathtop(V, -1), in(V, -1), out(V, -1){} }; struct Tree { int n; vector> gr; vector> chi; vector> par_exp; vector al; vector euler; vector par; vector dep; vector subsize; HLdecomposition hl; Tree() {} Tree(int input) { n = input; gr = vector>(n); par = vector(n); dep = vector(n); chi = vector>(n); } Tree(vector> gr) { par = vector(n); dep = vector(n); chi = vector>(n); int st = 0; int now = st; vector al(n); al[now] = 1; queue q; q.push(now); while(!q.empty()) { now = q.front(); q.pop(); rep(i,0,(ll)gr[now].size()) { int ne = gr[now][i]; if(!al[ne]) { connect(now, ne); q.push(ne); al[ne] = 1; } } } } void connect(int s,int t) { gr[s].push_back(t); gr[t].push_back(s); } void init_dfs (int d) { int len = gr[d].size(); int sum_subsize = 0; rep(i,0,len) { if(al[gr[d][i]]) continue; al[gr[d][i]] = 1; par[gr[d][i]] = d; dep[gr[d][i]] = dep[d] + 1; chi[d].push_back(gr[d][i]); euler.push_back(d); init_dfs(gr[d][i]); sum_subsize += subsize[gr[d][i]]; } subsize[d] = sum_subsize + 1; euler.push_back(d); } void make(int root) { rep(i,0,n) sort(ALL(gr[i])); al = vector(n,0); par = vector(n); dep = vector(n); subsize = vector(n); chi = vector>(n); euler = {}; al[root] = 1; par[root] = -1; dep[root] = 0; init_dfs(root); } int rad() { int max_ind = -1, max_dep = -1; int s,t; rep(i,0,n) if(chmax(max_dep, dep[i])) max_ind = i; make(max_ind); s = max_ind; max_ind = -1,max_dep = -1; rep(i,0,n) if(chmax(max_dep, dep[i])) max_ind = i; t = max_ind; swap(s,t); return max_dep; //return make_pair(s,t); } void init_lca() { int ct = 0; while(n >= (1<>(ct,vector(n,-1)); rep(i,0,n) par_exp[0][i] = par[i]; rep(i,0,ct-1){ rep(j,0,n){ if(par_exp[i][j] == -1) par_exp[i+1][j] = -1; else par_exp[i+1][j] = par_exp[i][par_exp[i][j]]; } } } int lca(int u,int v) { int h = par_exp.size(); if(dep[u] > dep[v]) swap(u,v); for(int i=h-1; i>=0; i--) { if(((dep[v]-dep[u])>>i)&1) v = par_exp[i][v]; } if(u == v) return u; for(int i=h-1;i>=0;i--) { if(par_exp[i][u] != par_exp[i][v]){ u = par_exp[i][u]; v = par_exp[i][v]; } } return par_exp[0][u]; } void dfs_(int d) { // dfs template int len = gr[d].size(); rep(i,0,len) { if(al[gr[d][i]]) continue; al[gr[d][i]] = 1; dfs_(gr[d][i]); } } void dfs(int root) { al = vector(n); al[root] = 1; dfs_(root); } void bfs(int root) { // bfs template al = vector(n); al[root] = 1; queue q; stack st; q.push(root); st.push(root); vector order; while(!q.empty()) { int d = q.front(); order.pb(d); // 今見ている頂点 q.pop(); int len = gr[d].size(); rep(i,0,len) { if(al[gr[d][i]]) continue; al[gr[d][i]] = 1; q.push(gr[d][i]); st.push(gr[d][i]); // ここで次の頂点を見ている } } while(!st.empty()) { int d = st.top(); st.pop(); order.pb(d); // ここでbfsの逆順に頂点をたどっている } } }; /* 使い方 */ /* Tree tr(n) // 宣言: n は頂点数 tr.connect(a,b) // 頂点 a と b をつなぐ tr.make(k) // 頂点 k を根としてpar,dep,chiを作り上げる tr.init_lca() // lcaを使う前に必ずこれをする tr.lca(a,b) // 頂点aとbの共通の"先祖"で一番近い"頂点"を返す tr.rad() // 木の直径を返す */ struct S {ll value, size;}; using F = ll; S fx(S l, S r) { return {l.value + r.value, l.size + r.size}; } S ex() { return {0, 0}; } S fa(F f, S x) { return {x.value + x.size * f, x.size}; } F fm(F f, F g) { return (f + g); } // gにfを加えるイメージ F em() { return 0; } void sol() { int n; cin >> n; HLdecomposition hl(n); rep(i,0,n-1) { int qw,er; cin >> qw >> er; qw--,er--; hl.add_edge(qw,er); } hl.build(0); vector v(n, {0, 1}); lazy_segtree st(v); auto f = [&](int l, int r){ st.apply(l,r,1); }; int q;cin >> q; while(q--) { int qw,er; cin >> qw >> er; qw--,er--; hl.path_query(qw,er,f); } ll ans = 0; rep(i,0,n) { ll qw = st.get(i).value; //cerr << qw << endl; ans += qw * (qw + 1) / 2; } cout << ans << endl; } int main() { init(); int q = 1; //cin >> q; while(q--) sol(); return 0; }