using System; using System.IO; using System.Linq; using System.Text; using System.Text.RegularExpressions; using System.Collections.Generic; using System.Diagnostics; using System.Numerics; using Enu = System.Linq.Enumerable; public class Program { public void Solve() { int N = Reader.Int(); var HL = new HeavyLightDecomposition(N); foreach (var t in Reader.IntTable(N - 1)) HL.AddEdge(--t[0], --t[1]); HL.Build(); int Q = Reader.Int(); long ans = 0; foreach (var t in Reader.IntTable(Q)) { HL.Add(--t[0], --t[1], 1); ans += HL.Sum(t[0], t[1]); } Console.WriteLine(ans); } class HeavyLightDecomposition { public readonly int N; List[] E; int[] Y, X, Size, Parent; List> Path = new List>(); // debug List PathDepth = new List(); RangeAddSumSegTree[] seg; void Init() { seg = new RangeAddSumSegTree[Path.Count]; for (int i = 0; i < seg.Length; i++) seg[i] = new RangeAddSumSegTree(Path[i].Count); } public void Add(int a, int b, long val) { int pa = Y[a], pb = Y[b]; if (pa == pb) seg[pa].Add(Math.Min(X[a], X[b]), Math.Max(X[a], X[b]) + 1, val); else if (PathDepth[pa] >= PathDepth[pb]) { seg[pa].Add(0, X[a] + 1, val); Add(Parent[Path[pa][0]], b, val); } else { seg[pb].Add(0, X[b] + 1, val); Add(Parent[Path[pb][0]], a, val); } } public long Sum(int a, int b) { int pa = Y[a], pb = Y[b]; if (pa == pb) return seg[pa].Sum(Math.Min(X[a], X[b]), Math.Max(X[a], X[b]) + 1); if (PathDepth[pa] >= PathDepth[pb]) return seg[pa].Sum(0, X[a] + 1) + Sum(Parent[Path[pa][0]], b); return seg[pb].Sum(0, X[b] + 1) + Sum(Parent[Path[pb][0]], a); } public HeavyLightDecomposition(int n) { N = n; Y = new int[N]; X = new int[N]; Size = new int[N]; Parent = new int[N]; E = new List[N]; for (int i = 0; i < N; i++) E[i] = new List(); } public void AddEdge(int a, int b) { E[a].Add(b); E[b].Add(a); } public void Build(int root = 0) { CountNodes(); CompressPath(); Init(); } void CountNodes() { var stack = new Stack(); var nodes = new int[N]; int ni = N - 1; stack.Push(0); while (stack.Count > 0) { int a = stack.Pop(); for (int ei = 0; ei < E[a].Count; ei++) { int b = E[a][ei]; if (b == Parent[a]) { E[a].RemoveAt(ei); ei--; } else { Parent[b] = a; stack.Push(b); } } nodes[ni--] = a; } foreach (int a in nodes) { Size[a] = 1; var e = E[a]; for (int i = 0; i < e.Count; i++) { int b = E[a][i]; Size[a] += Size[b]; if (Size[b] > Size[e[0]]) { int t = e[0]; e[0] = b; e[i] = t; } } } } void CompressPath() { var stack = new Stack(); stack.Push(0); Path.Add(new List()); PathDepth.Add(0); while (stack.Count > 0) { long mask = stack.Pop(); int a = (int)(mask >> 32); int pathId = (int)mask; Y[a] = pathId; X[a] = Path[pathId].Count; Path[pathId].Add(a); if (E[a].Count == 0) continue; for (int i = E[a].Count - 1; i > 0; i--) { Path.Add(new List()); PathDepth.Add(PathDepth[pathId] + 1); stack.Push(((long)E[a][i] << 32) + Path.Count - 1); } stack.Push(((long)E[a][0] << 32) + pathId); } } public int LCA(int a, int b) { int pa = Y[a], pb = Y[b]; if (pa == pb) return (X[a] < X[b]) ? a : b; if (PathDepth[pa] >= PathDepth[pb]) return LCA(Parent[Path[pa][0]], b); return LCA(a, Parent[Path[pb][0]]); } } class RangeAddSumSegTree { public readonly int N; private readonly long[] V, S; public RangeAddSumSegTree(int n) { for (N = 2; N < n; ) N *= 2; V = new long[N * 2]; S = new long[N * 2]; } // [L, R) public long Sum(int L, int R) { return Sum(0, 0, N, L, R); } private long Sum(int i, int currL, int currR, int L, int R) { if (currL >= R || currR <= L) return 0; if (currL >= L && currR <= R) return V[i] * (currR - currL) + S[i]; long res = V[i] * (Math.Min(currR, R) - Math.Max(currL, L)); int mid = (currL + currR) / 2; res += Sum(i * 2 + 1, currL, mid, L, R); res += Sum(i * 2 + 2, mid, currR, L, R); return res; } // [L, R) public void Add(int L, int R, long val) { Add(0, val, 0, N, L, R); } private void Add(int i, long val, int currL, int currR, int L, int R) { if (currL >= R || currR <= L) return; if (currL >= L && currR <= R) { V[i] += val; return; } S[i] += val * (Math.Min(currR, R) - Math.Max(currL, L)); int mid = (currL + currR) / 2; Add(i * 2 + 1, val, currL, mid, L, R); Add(i * 2 + 2, val, mid, currR, L, R); } } } class Entry { static void Main() { new Program().Solve(); } } class Reader { static TextReader reader = Console.In; static readonly char[] separator = { ' ' }; static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries; static string[] A = new string[0]; static int i; static void Init() { A = new string[0]; } public static void Set(TextReader r) { reader = r; Init(); } public static void Set(string file) { reader = new StreamReader(file); Init(); } public static bool HasNext() { return CheckNext(); } public static string String() { return Next(); } public static int Int() { return int.Parse(Next()); } public static long Long() { return long.Parse(Next()); } public static double Double() { return double.Parse(Next()); } public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); } public static int[] IntArray(int N) { return Range(N, Int); } public static int[][] IntTable(int H) { return Range(H, IntLine); } public static string[] StringArray(int N) { return Range(N, Next); } public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); } public static string Line() { return reader.ReadLine().Trim(); } static string[] Split(string s) { return s.Split(separator, op); } static T[] Range(int N, Func f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()); return r; } static string Next() { CheckNext(); return A[i++]; } static bool CheckNext() { if (i < A.Length) return true; string line = reader.ReadLine(); if (line == null) return false; if (line == "") return CheckNext(); A = Split(line); i = 0; return true; } }