import static java.lang.Math.*; import static java.util.Arrays.*; import java.io.*; import java.lang.reflect.Array; import java.math.BigInteger; import java.util.*; import java.util.concurrent.ThreadLocalRandom; import java.util.function.*; import java.util.stream.IntStream; class Solver{ long st = System.currentTimeMillis(); long elapsed(){ return System.currentTimeMillis() -st; } void reset(){ st = System.currentTimeMillis(); } final static int infI = (1 <<30) -1; final static long infL = 1L <<60; // final static long mod = (int) 1e9 +7; final static long mod = 998244353; final static String yes = "Yes"; final static String no = "No"; static Random rd = ThreadLocalRandom.current(); MyReader in = new MyReader(System.in); MyWriter out = new MyWriter(System.out); MyWriter log = new MyWriter(System.err){ @Override void println(Object obj){ super.println(obj == null ? "null" : obj); }; @Override protected void ln(){ super.ln(); flush(); }; }; Object solve(){ int N = in.it(); DualSegmentTree seg = new DualSegmentTree<>(N){ @Override protected Long e(){ return 0L; } protected Long agg(Long v0,Long v1){ return v0 +v1; } @Override protected Long comp(Long f0,Long f1){ return f0 +f1; } @Override protected Long map(Long v,Long f,int l,int r){ return v +f; } }; var hld = new HLD(N,seg); for (int i = 1;i < N;i++) hld.addEdge(in.idx(),in.idx()); hld.makeTree(0); int Q = in.it(); while (Q-- > 0) { int u = in.idx(); int v = in.idx(); hld.updPath(u,v,true,1L); } long ans = 0; for (int i = 0;i < N;i++) { Long t = hld.getNode(i); ans += t++ *t /2; } return ans; } } abstract class DualSegmentTree extends Seg{ DualSegmentTree(int n){ super(n); } @Override protected abstract V map(V v,F f,int l,int r); @Override protected abstract F comp(F f0,F f1); @Override protected void rangeMap(int i){} @Override protected void upd(int i,F f){ upd(i,i +1,f); } @Override protected void upd(int l,int r,F f){ down(l,r); super.upd(l,r,f); } @Override protected V get(int i){ down(i,i +1); return super.get(i); } } abstract class LazySegmentTree extends Seg{ LazySegmentTree(int n){ super(n); } @Override protected abstract V agg(V v0,V v1); @Override protected abstract V map(V v,F f,int l,int r); @Override protected abstract F comp(F f0,F f1); @Override protected void upd(int i,F f){ upd(i,i +1,f); } @Override protected void upd(int l,int r,F f){ down(l,r); super.upd(l,r,f); up(l,r); } @Override protected V get(int i){ return get(i,i +1); } @Override protected V get(int l,int r){ down(l,r); return super.get(l,r); } } class HLD extends Graph{ Seg lft; private Seg rht; HLD(int n,Seg seg){ this(n,seg,seg); } HLD(int n,Seg lft,Seg rht){ super(n,false); this.lft = lft; this.rht = rht; } public void updNode(int u,F f){ upd(nds[u],f); } public void updEdge(int e,F f){ upd(es.get(e),f); } public void upd(Nd nd,F f){ lft.upd(nd.l,f); if (lft != rht) rht.upd(nd.l,f); } public void updPath(int ui,int vi,boolean incLca,F f){ Node u = nds[ui],v = nds[vi]; while (true) { if (u.l > v.l) { var t = u; u = v; v = t; } var h = v.hp; if (h.l <= u.l) { lft.upd(u.l +(incLca ? 0 : 1),v.l +1,f); if (lft != rht) rht.upd(u.l +(incLca ? 0 : 1),v.l +1,f); return; } lft.upd(h.l,v.l +1,f); if (lft != rht) rht.upd(h.l,v.l +1,f); v = h.p; } } public V getPath(int ui,int vi,boolean incLca){ Node u = nds[ui],v = nds[vi]; V vl = lft.e(),vr = lft.e(); boolean tog = false; while (true) { if (u.l > v.l) { var t = u; u = v; v = t; tog ^= true; } var h = v.hp; if (h.l <= u.l) { if (tog) vl = rht.agg(vl,lft.get(u.l +(incLca ? 0 : 1),v.l +1)); else vr = rht.agg(rht.get(u.l +(incLca ? 0 : 1),v.l +1),vr); return rht.agg(vl,vr); } if (tog) vl = rht.agg(vl,lft.get(h.l,v.l +1)); else vr = rht.agg(rht.get(h.l,v.l +1),vr); v = h.p; } } public V getSub(int ui,boolean incLca){ return lft.get(nds[ui].l +(incLca ? 0 : 1),nds[ui].r); } public V getNode(int ui){ return lft.get(nds[ui].l); } public V get(Node u){ return lft.get(u.l); } int lca(int ui,int vi){ Node u = nds[ui],v = nds[vi]; while (true) { if (u.l > v.l) { var t = u; u = v; v = t; } var h = v.hp; if (h.l <= u.l) return u.id; v = h.p; } } public void makeTree(int si){ Stack stk = new Stack<>(); var s = nds[si]; s.p = s; stk.add(s); stk.add(s); while (!stk.isEmpty()) { var u = stk.pop(); if (u.r < 1) { u.r = 1; for (var e:go(u.id)) { if (e.v == u.p) continue; es.set(e.id,e); e.v.p = u; stk.add(e.v); stk.add(e.v); } } else if (u != s) u.p.r += u.r; } for (var u:nds) { var go = go(u.id); for (int i = 1;i < go.size();i++) if (u.r < go.get(0).v.r || go.get(0).v.r < go.get(i).v.r && go.get(i).v.r < u.r) Collections.swap(go,0,i); } int hid = 0; stk.add(s); while (!stk.isEmpty()) { var u = stk.pop(); u.r += u.l = hid; if (u.hp == null) u.hp = u; hid++; var go = go(u.id); for (int i = go.size();i-- > 0;) { var v = go.get(i).v; if (v == u.p) continue; if (i == 0) v.hp = u.hp; stk.add(v); } } for (var e:es) { e.l = e.v.l; e.r = e.v.r; } } } abstract class Seg { protected int n,log; private V[] val; private F[] lazy; private int[] l,r; @SuppressWarnings("unchecked") Seg(int n){ this.n = n; while (1 < 0;l[i] = l[i <<1],r[i] = r[i <<1 |1]) merge(i); } protected abstract V e(); protected V init(int i){ return e(); } protected V agg(V v0,V v1){ return null; } protected V map(V v,F f,int l,int r){ return null; } protected void rangeMap(int i){ val[i] = map(val[i],lazy[i],l[i],r[i]); } protected F comp(F f0,F f1){ return null; } protected V eval(int i){ if (i < n && lazy[i] != null) { rangeMap(i); prop(i <<1,lazy[i]); prop(i <<1 |1,lazy[i]); lazy[i] = null; } return val[i]; } private void merge(int i){ val[i] = agg(eval(i <<1),eval(i <<1 |1)); } protected void prop(int i,F f){ if (i < n) lazy[i] = lazy[i] == null ? f : comp(lazy[i],f); else val[i] = map(val[i],f,l[i],r[i]); } protected void up(int l,int r){ l = oddPart(l +n); r = oddPart(r +n); while (1 < l) merge(l >>= 1); while (1 < r) merge(r >>= 1); } protected void down(int l,int r){ l = oddPart(l +n); r = oddPart(r +n); for (int i = log;i > 0;i--) { if (l >>i > 0) eval(l >>i); if (r >>i > 0) eval(r >>i); } } private int oddPart(int i){ return i /(i &-i); } protected void upd(int i,F f){ prop(i +n,f); } protected void upd(int l,int r,F f){ l += n; r += n; do { if ((l &1) == 1) prop(l++,f); if ((r &1) == 1) prop(--r,f); } while ((l >>= 1) < (r >>= 1)); } protected V get(int i){ return val[i +n]; } protected V get(int l,int r){ l += n; r += n; V vl = e(),vr = e(); while (l < r) { vl = (l &1) == 0 ? vl : agg(vl,eval(l++)); vr = (r &1) == 0 ? vr : agg(eval(--r),vr); l >>= 1; r >>= 1; } return agg(vl,vr); } } abstract class SegmentTree extends Seg{ SegmentTree(int n){ super(n); } @Override protected abstract V agg(V v0,V v1); @Override protected abstract V map(V v,F f,int l,int r); @Override protected void upd(int i,F f){ super.upd(i,f); up(i,i +1); } } class Edge extends Nd{ Node u,v; L val; Edge(int id,Node u,Node v,L val){ super(id); this.u = u; this.v = v; this.val = val; } @Override public String toString(){ return "(" +u.id +"," +v.id +")"; } } class Node extends Nd{ Node p,hp; Node(int id){ super(id); } @Override public String toString(){ return "" +id; } } class Nd{ int id,l,r; Nd(int id){ this.id = id; } } class Graph { public int n; List> es; Node[] nds; private List>> go,back; public Graph(int n,boolean dir){ this.n = n; nds = new Node[n]; go = new ArrayList<>(); back = dir ? new ArrayList<>() : go; for (int i = 0;i < n;i++) { nds[i] = new Node(i); go.add(new ArrayList<>()); back.add(new ArrayList<>()); } es = new ArrayList<>(); } public void addEdge(int u,int v){ addEdge(u,v,null); } public void addEdge(int u,int v,L l){ Edge e = new Edge<>(es.size(),nds[u],nds[v],l); es.add(e); go.get(u).add(e); back.get(v).add(new Edge<>(e.id,e.v,e.u,e.val)); } public List> go(int ui){ return go.get(ui); } public List> back(int ui){ return back.get(ui); } } class Util{ static char[] arrC(int N,IntUnaryOperator f){ char[] ret = new char[N]; for (int i = 0;i < N;i++) ret[i] = (char) f.applyAsInt(i); return ret; } static int[] arrI(int N,IntUnaryOperator f){ int[] ret = new int[N]; setAll(ret,f); return ret; } static long[] arrL(int N,IntToLongFunction f){ long[] ret = new long[N]; setAll(ret,f); return ret; } static double[] arrD(int N,IntToDoubleFunction f){ double[] ret = new double[N]; setAll(ret,f); return ret; } static T[] arr(T[] arr,IntFunction f){ setAll(arr,f); return arr; } } class MyReader{ private byte[] buf = new byte[1 <<16]; private int ptr = 0; private int tail = 0; private InputStream in; MyReader(InputStream in){ this.in = in; } private byte read(){ if (ptr == tail) try { tail = in.read(buf); ptr = 0; } catch (IOException e) {} return buf[ptr++]; } private boolean isPrintable(byte c){ return 32 < c && c < 127; } private byte nextPrintable(){ byte ret = read(); while (!isPrintable(ret)) ret = read(); return ret; } int it(){ return toIntExact(lg()); } int[] it(int N){ return Util.arrI(N,i -> it()); } int[][] it(int H,int W){ return Util.arr(new int[H][],i -> it(W)); } int idx(){ return it() -1; } int[] idx(int N){ return Util.arrI(N,i -> idx()); } int[][] idx(int H,int W){ return Util.arr(new int[H][],i -> idx(W)); } long lg(){ byte i = nextPrintable(); boolean negative = i == 45; long n = negative ? 0 : i -'0'; while (isPrintable(i = read())) n = 10 *n +i -'0'; return negative ? -n : n; } long[] lg(int N){ return Util.arrL(N,i -> lg()); } long[][] lg(int H,int W){ return Util.arr(new long[H][],i -> lg(W)); } double dbl(){ return Double.parseDouble(str()); } double[] dbl(int N){ return Util.arrD(N,i -> dbl()); } double[][] dbl(int H,int W){ return Util.arr(new double[H][],i -> dbl(W)); } char[] ch(){ return str().toCharArray(); } char[][] ch(int H){ return Util.arr(new char[H][],i -> ch()); } String line(){ StringBuilder sb = new StringBuilder(); for (byte c;(c = read()) != '\n';) sb.append((char) c); return sb.toString(); } String str(){ StringBuilder sb = new StringBuilder(); sb.append((char) nextPrintable()); for (byte c;isPrintable(c = read());) sb.append((char) c); return sb.toString(); } String[] str(int N){ return Util.arr(new String[N],i -> str()); } } class MyWriter{ OutputStream out; byte[] buf = new byte[1 <<16]; byte[] ibuf = new byte[20]; int tail = 0; MyWriter(OutputStream out){ this.out = out; } void flush(){ try { out.write(buf,0,tail); tail = 0; } catch (IOException e) { e.printStackTrace(); } } protected void ln(){ write((byte) '\n'); } private void write(byte b){ buf[tail++] = b; if (tail == buf.length) flush(); } private void write(byte[] b,int off,int len){ for (int i = off;i < off +len;i++) write(b[i]); } private void write(long n){ if (n < 0) { n = -n; write((byte) '-'); } int i = ibuf.length; do { ibuf[--i] = (byte) (n %10 +'0'); n /= 10; } while (n > 0); write(ibuf,i,ibuf.length -i); } private void print(Object obj){ if (obj instanceof Boolean) print((boolean) obj ? Solver.yes : Solver.no); else if (obj instanceof Integer) write((int) obj); else if (obj instanceof Long) write((long) obj); else if (obj instanceof char[] cs) for (char b:cs) write((byte) b); else if (obj.getClass().isArray()) { int l = Array.getLength(obj); for (int i = 0;i < l;i++) { print(Array.get(obj,i)); if (i +1 < l) write((byte) ' '); } } else print(Objects.toString(obj).toCharArray()); } void println(Object obj){ if (obj == null) return; if (obj instanceof Collection co) for (Object e:co) println(e); else if (obj.getClass().isArray() && Array.getLength(obj) > 0 && Array.get(obj,0).getClass().isArray()) { int l = Array.getLength(obj); for (int i = 0;i < l;i++) println(Array.get(obj,i)); } else { print(obj); ln(); } } void printlns(Object... o){ print(o); ln(); } } class Main{ public static void main(String[] args) throws Exception{ new Solver(){ public void exe(){ out.println(solve()); // Optional.ofNullable(solve()).ifPresent(System.out::println); out.flush(); log.println(elapsed()); } }.exe(); } }