using System; using System.Linq; using System.Linq.Expressions; using System.Collections.Generic; using Debug = System.Diagnostics.Debug; using StringBuilder = System.Text.StringBuilder; using System.Numerics; using Number = System.Int64; namespace Program { public class Solver { public void Solve() { var n = sc.Integer(); var G = new HLTreeGraph(n); for (int i = 0; i < n - 1; i++) { G.AddEdge(sc.Integer() - 1, sc.Integer() - 1); } G.Build(0); var q = sc.Integer(); Debug.WriteLine(q); long ans = 0; for (int i = 0; i < q; i++) { var val = G.Query(sc.Integer() - 1, sc.Integer() - 1); Debug.WriteLine(val); ans += val; } IO.Printer.Out.WriteLine(ans); } public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput()); static T[] Enumerate(int n, Func f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; } static public void Swap(ref T a, ref T b) { var tmp = a; a = b; b = tmp; } } } #region main static class Ex { static public string AsString(this IEnumerable ie) { return new string(System.Linq.Enumerable.ToArray(ie)); } static public string AsJoinedString(this IEnumerable ie, string st = " ") { return string.Join(st, ie); } static public void Main() { var solver = new Program.Solver(); solver.Solve(); Program.IO.Printer.Out.Flush(); } } #endregion #region Ex namespace Program.IO { using System.IO; using System.Text; using System.Globalization; public class Printer: StreamWriter { static Printer() { Out = new Printer(Console.OpenStandardOutput()) { AutoFlush = false }; } public static Printer Out { get; set; } public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } } public Printer(System.IO.Stream stream) : base(stream, new UTF8Encoding(false, true)) { } public Printer(System.IO.Stream stream, Encoding encoding) : base(stream, encoding) { } public void Write(string format, T[] source) { base.Write(format, source.OfType().ToArray()); } public void WriteLine(string format, T[] source) { base.WriteLine(format, source.OfType().ToArray()); } } public class StreamScanner { public StreamScanner(Stream stream) { str = stream; } public readonly Stream str; private readonly byte[] buf = new byte[1024]; private int len, ptr; public bool isEof = false; public bool IsEndOfStream { get { return isEof; } } private byte read() { if (isEof) return 0; if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } } return buf[ptr++]; } public char Char() { byte b = 0; do b = read(); while ((b < 33 || 126 < b) && !isEof); return (char)b; } public string Scan() { var sb = new StringBuilder(); for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b); return sb.ToString(); } public string ScanLine() { var sb = new StringBuilder(); for (var b = Char(); b != '\n'; b = (char)read()) if (b == 0) break; else if (b != '\r') sb.Append(b); return sb.ToString(); } public long Long() { if (isEof) return long.MinValue; long ret = 0; byte b = 0; var ng = false; do b = read(); while (b != 0 && b != '-' && (b < '0' || '9' < b)); if (b == 0) return long.MinValue; if (b == '-') { ng = true; b = read(); } for (; true; b = read()) { if (b < '0' || '9' < b) return ng ? -ret : ret; else ret = ret * 10 + b - '0'; } } public int Integer() { return (isEof) ? int.MinValue : (int)Long(); } public double Double() { var s = Scan(); return s != "" ? double.Parse(s, CultureInfo.InvariantCulture) : double.NaN; } private T[] enumerate(int n, Func f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(); return a; } public char[] Char(int n) { return enumerate(n, Char); } public string[] Scan(int n) { return enumerate(n, Scan); } public double[] Double(int n) { return enumerate(n, Double); } public int[] Integer(int n) { return enumerate(n, Integer); } public long[] Long(int n) { return enumerate(n, Long); } } } #endregion #region HLTreeGraph public class HLTreeGraph { int N, M; List[] G; List H = new List(); int[] subTreeSize; int[] par; int[] pos; public int[] d; int[] ord; //chain id Chain[] go; //chain's parent int[] hlpar; public HLTreeGraph(int n) { N = n; G = Enumerate(n, x => new List()); subTreeSize = new int[n]; pos = new int[n]; d = new int[n]; par = new int[n]; go = new Chain[n]; ord = new int[n]; } public void AddEdge(int f, int t) { G[f].Add(new Edge(f, t)); G[t].Add(new Edge(t, f)); } #region impl public void Build(int root) { ComputeSubTreeSize(root); Decomposite(new Edge(-1, root), -1, 0, 0); return; M = H.Count; BuildHLLCA(); } public void ComputeSubTreeSize(int root) { var ord = new int[N]; par[root] = -1; d[root] = 0; var ptr = 0; var last = 0; ord[last++] = root; while (ptr < last) { var p = ord[ptr++]; foreach (var to in G[p]) { if (to.to != par[p]) { par[to.to] = p; d[to.to] = d[p] + 1; ord[last++] = to.to; } } } for (int i = N - 1; i > 0; i--) { subTreeSize[i] += 1; subTreeSize[par[i]] += subTreeSize[i]; } } public void Decomposite(Edge light, int prevId, int d, int lv) { var chain = new Chain() { light = light, id = H.Count, parId = prevId, level = lv }; H.Add(chain); var prev = light.from; var cur = light.to; while (cur != prev) { var next = cur; var max = 0; go[cur] = chain; pos[cur] = chain.heavy.Count; foreach (var to in G[cur]) { var t = to.to; if (t != prev) max = Math.Max(max, subTreeSize[t]); } foreach (var to in G[cur]) { var t = to.to; if (t == prev) continue; if (max == subTreeSize[t]) { //Debug.WriteLine("{0}->{1}", cur, t); max = 1 << 30; next = t; chain.heavy.Add(to); } else Decomposite(to, chain.id, d + 1, lv + 1); } prev = cur; cur = next; d++; } chain.init(this); } const int HLHEIGHT = 8; void BuildHLLCA() { if (H.Max(x => x.level) > 1 << 7) throw new Exception(); hlpar = new int[HLHEIGHT * M]; for (int k = 0; k < HLHEIGHT; k++) for (int v = 0; v < M; v++) hlpar[k * M + v] = -1; for (int i = 0; i < M; i++) hlpar[i] = H[i].parId; for (int k = 1; k < HLHEIGHT; k++) for (int v = 0; v < M; v++) if (hlpar[(k - 1) * M + v] >= 0) hlpar[k * M + v] = hlpar[(k - 1) * M + hlpar[(k - 1) * M + v]]; } public int GetAncestorAt(Chain v, int lv) { var id = v.id; var d = v.level - lv; for (int i = 0; i < HLHEIGHT; i++) if ((d >> i & 1) == 1) id = hlpar[i * M + id]; return id; } public long Query(int u, int v) { long ans = 0; ans += d[u]; ans += d[v]; while (go[u].id != go[v].id) { if (go[u].level > go[v].level) { ans += go[u].seg[pos[u] + 1]; go[u].seg.Add(1, pos[u] + 1, 1); u = go[u].light.from; } else { ans += go[v].seg[pos[v] + 1]; go[v].seg.Add(1, pos[v] + 1, 1); v = go[v].light.from; } } if (pos[u] < pos[v]) ans += -2 * d[u] + 1; else ans += -2 * d[v] + 1; var min = Math.Min(pos[u], pos[v]); var max = Math.Max(pos[u], pos[v]); ans += go[u].seg[min + 1, max + 1]; go[u].seg.Add(min + 1, max + 1, 1); return ans; } public int GetLCA(int u, int v) { if (go[u].level > go[v].level) { var tmp = u; u = v; v = tmp; } if (go[u].level < go[v].level) v = H[GetAncestorAt(go[v], go[u].level + 1)].light.from; if (go[u].id == go[v].id) { if (d[u] <= d[v]) return u; else return v; } //HL { u = go[u].id; v = go[v].id; for (int i = HLHEIGHT - 1; i >= 0; i--) { if (hlpar[i * M + u] != hlpar[i * M + v]) { u = hlpar[i * M + u]; v = hlpar[i * M + v]; } } for (int i = HLHEIGHT - 1; i >= 0; i--) { if (hlpar[i * M + u] != hlpar[i * M + v]) { u = hlpar[i * M + u]; v = hlpar[i * M + v]; } } } //Tree { u = H[u].light.from; v = H[v].light.from; } if (d[u] <= d[v]) return u; else return v; } static T[] Enumerate(int n, Func f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; } #endregion } public class Chain { public Edge light; public List heavy = new List(); public int parId; public int level; public int id; public RangeAddFenwickTree seg; public void init(HLTreeGraph G) { seg = new RangeAddFenwickTree(heavy.Count + 2); } public override string ToString() { var s = new List(); s.Add(light.from); s.Add(light.to); foreach (var e in heavy) s.Add(e.to); return s.AsJoinedString("->"); } } #endregion #region TreeEdge public struct Edge { public int from, to; public Edge(int f, int t) { from = f; to = t; } public override string ToString() { return string.Format("{0}->{1}", from, to); } } #endregion #region FenwickTree [System.Diagnostics.DebuggerDisplay("Data={ToString()}")] public class FenwickTree { int n; long[] bit; int max = 1; public FenwickTree(int size) { n = size; bit = new long[n + 1]; while ((max << 1) <= n) max <<= 1; } /// sum[a,b] public long this[int i, int j] { get { return this[j] - this[i - 1]; } } /// sum[0,i] public long this[int i] { get { long s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; } } public int LowerBound(long w) { if (w <= 0) return 0; int x = 0; for (int k = max; k > 0; k >>= 1) if (x + k <= n && bit[x + k] < w) { w -= bit[x + k]; x += k; } return x + 1; } /// add v to bit[i] public void Add(int i, long v) { if (i == 0) System.Diagnostics.Debug.Fail("BIT is 1 indexed"); for (; i <= n; i += i & -i) bit[i] += v; } public override string ToString() { return string.Join(",", Enumerable.Range(0, n + 1).Select(i => this[i, i])); } } #endregion #region RangeAddFenwickTree public class RangeAddFenwickTree { int n; FenwickTree a, b; public RangeAddFenwickTree(int n) { this.n = n; a = new FenwickTree(n); b = new FenwickTree(n); } /// Add V to[i,j] public void Add(int i, int j, long v) { a.Add(i, -(i - 1) * v); a.Add(j + 1, j * v); b.Add(i, v); b.Add(j + 1, -v); } /// Sum [0,i] public long this[int i] { get { return a[i] + b[i] * i; } } /// Sum [i,j] public long this[int i, int j] { get { return this[j] - this[i - 1]; } } public override string ToString() { return string.Join(",", Enumerable.Range(0, n + 1).Select(i => this[i, i])); } } #endregion