using Qlibrary; using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.Globalization; using System.IO; using System.Linq; using System.Numerics; using System.Runtime.CompilerServices; using System.Text; using static Qlibrary.Common; using static Qlibrary.MathPlus; namespace Qompetitive { internal static class Program { private static void Main(string[] args) { SourceExpander.Expander.Expand(); checked { int n = Si(); int[][] uv = Sqi(n - 1, 2); int q = Si(); int[][] ab = Sqi(q, 2); var g = new Graph(n, uv, false); var ls = new LazyHeavyLightTree(g); ls.InitForVertex(); ls.MappingVertex = t => t.Current + t.Lazy * t.length; ls.CompositionVertex = t => t.F + t.G; ls.OperationVertex = t => t.A + t.B; long ans = 0; foreach (var i in ab) { ls.UpdateVertexOfPath(i[0], i[1], 1); } for (int i = 0; i < g.Count; i++) { var o = ls.vertexSegTree.Query(i,i); if (o == 0) { continue; } ans += ArithmeticSum(o); } Console.WriteLine(ans); } } } } // SourceExpander | MIT License | https://github.com/kzrnm/SourceExpander/blob/master/LICENSE #region Expanded by https://github.com/kzrnm/SourceExpander namespace Qlibrary { public static class Common { public const int Power9 = 1000000000; public const long Power18 = 1000000000000000000L; public const int InfinityInt = 1 * Power9; public const long Infinity = 4 * Power18; public static readonly StreamScanner Scanner = new StreamScanner(Console.OpenStandardInput()); public static int Si() => Scanner.Integer(); public static long Sl() => Scanner.Long(); public static string Ss() => Scanner.Scan(); public static int[] Sai(int count) => Scanner.ArrayInt(count); public static long[] Sal(int count) => Scanner.ArrayLong(count); public static int[][] Sqi(int yCount, int xCount) => Scanner.SquareInt(yCount, xCount); public static long[][] Sql(int yCount, int xCount) => Scanner.SquareLong(yCount, xCount); public static string[] Sss(int count) => Enumerable.Repeat(0, count).Select(_ => Ss()).ToArray(); public static T[] Make(int n, Func creator) => Enumerable.Repeat(0, n).Select(_ => creator()).ToArray(); [MethodImpl(256)] public static (T, T) SorTuple(T a, T b) where T : IComparable => a.CompareTo(b) < 0 ? (a, b) : (b, a); [MethodImpl(256)] public static (T, T) SorTuple((T, T) t) where T : IComparable => SorTuple(t.Item1, t.Item2); [MethodImpl(256)] public static void Loop(long n, Action action) { for (int i = 0; i < n; i++) { action(); } } [MethodImpl(256)] public static T GetInfinity() where T : INumberBase { return T.Zero switch { int => T.CreateSaturating(InfinityInt), long => T.CreateSaturating(Infinity), double => T.CreateSaturating(double.MaxValue / 2.1), decimal => T.CreateSaturating(decimal.MaxValue / 2.1m), _ => T.CreateSaturating(long.MaxValue) / T.CreateSaturating(2.1)}; } [MethodImpl(256)] public static T GMin(T v1, T v2) where T : INumber => v1 <= v2 ? v1 : v2; [MethodImpl(256)] public static T GMax(T v1, T v2) where T : INumber => v1 >= v2 ? v1 : v2; private static T[, ] Rotate90(this T[, ] self) { int rows = self.GetLength(0); int columns = self.GetLength(1); var result = new T[columns, rows]; for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { result[j, rows - i - 1] = self[i, j]; } } return result; } public static T[, ] Rotate90(this T[, ] self, int count) { for (int i = 0; i < count; i++) { self = self.Rotate90(); } return self; } public static T[, ] Rotate90(this T[][] self, int count) { var rows = self.Length; var columns = self.First().Length; T[, ] array = new T[rows, columns]; for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { array[i, j] = self[i][j]; } } return Rotate90(array, count); } public static void SafeAdd(this Dictionary self, T1 key, Action action) where T2 : new() { if (!self.ContainsKey(key)) { self.Add(key, new T2()); } action(self[key]); } public static void Init(this T[] array, T value) => Array.Fill(array, value); public static void Init(this T[, ] array, T value) { var l1 = array.GetLength(0); var l2 = array.GetLength(1); for (int i = 0; i < l1; i++) { for (int j = 0; j < l2; j++) { array[i, j] = value; } } } public static void Init(this T[,, ] array, T value) { var l1 = array.GetLength(0); var l2 = array.GetLength(1); var l3 = array.GetLength(2); for (int i = 0; i < l1; i++) { for (int j = 0; j < l2; j++) { for (int k = 0; k < l3; k++) { array[i, j, k] = value; } } } } } } namespace Qlibrary { public class StreamScanner { private const int Size = 1024 * 16; public StreamScanner(Stream stream) { str = stream; } private readonly Stream str; private readonly byte[] buf = new byte[Size]; private int len, ptr; public bool IsEof { get; private set; } private byte Read() { if (IsEof) throw new EndOfStreamException(); if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, Size)) <= 0) { IsEof = true; return 0; } } return buf[ptr++]; } public char Char() { byte b = 0; do b = Read(); while (b < 33 || 126 < b); return (char)b; } public string Scan() { var sb = new StringBuilder(); for (char b = Char(); b >= 33 && b <= 126; b = (char)Read()) sb.Append(b); return sb.ToString(); } public string ScanIncludeSpace() { var sb = new StringBuilder(); for (char b = Char(); b >= 32 && b <= 126; b = (char)Read()) sb.Append(b); return sb.ToString(); } public long Long() { long ret = 0; byte b = 0; bool ng = false; do b = Read(); while (b != '-' && (b < '0' || '9' < b)); 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 (int)Long(); } public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); } public long[] ArrayLong(int count = 0) { long[] scan = new long[count]; for (int i = 0; i < count; i++) { scan[i] = Long(); } return scan; } public int[] ArrayInt(int count = 0) { int[] scan = new int[count]; for (int i = 0; i < count; i++) { scan[i] = Integer(); } return scan; } public long[][] SquareLong(int row, int col) { long[][] scan = new long[row][]; for (int i = 0; i < row; i++) { scan[i] = ArrayLong(col); } return scan; } public int[][] SquareInt(int row, int col) { int[][] scan = new int[row][]; for (int i = 0; i < row; i++) { scan[i] = ArrayInt(col); } return scan; } } } namespace Qlibrary { public class LazySegmentTree { private T[] data; private T[] lazyData; private int[] depth; public Func<(T A, T B), T> Operation { get; set; } public Func<(T Current, T Lazy, int length), T> Mapping { get; set; } public Func<(T F, T G), T> Composition { get; set; } public T E { get; set; } private int n; private int count; private int height = 0; public LazySegmentTree(int count, T e = default) { this.count = count; E = e; n = 1; while (n < count) { n <<= 1; height++; } data = Enumerable.Repeat(E, 2 * n - 1).ToArray(); lazyData = Enumerable.Repeat(E, 2 * n - 1).ToArray(); depth = new int[2 * n - 1]; var nd = MathPlus.Digit(n, 2); for (int i = 0; i < 2 * n - 1; i++) { depth[i] = 1 << (nd - MathPlus.Digit(i + 1, 2)); } } [MethodImpl(256)] public void Build(Func update) { for (int i = 0; i < count; i++) { data[n + i - 1] = update(i); } for (int i = n - 2; i >= 0; i--) { data[i] = Operation((data[2 * i + 1], data[2 * i + 2])); } } [MethodImpl(256)] private void Evaluate(int k) { if (lazyData[k].Equals(E)) { return; } if (k < n - 1) { lazyData[2 * k + 1] = Composition((lazyData[2 * k + 1], lazyData[k])); lazyData[2 * k + 2] = Composition((lazyData[2 * k + 2], lazyData[k])); } data[k] = Mapping((data[k], lazyData[k], depth[k])); lazyData[k] = E; } [MethodImpl(256)] public void Update(int left, int right, T value) { Update(left, right + 1, value, 0, 0, n); } [MethodImpl(256)] private void Update(int a, int b, T x, int k, int l, int r) { Evaluate(k); if (r <= a || b <= l) { return; } if (a <= l && r <= b) { lazyData[k] = Composition((lazyData[k], x)); Evaluate(k); } else { Update(a, b, x, 2 * k + 1, l, (l + r) / 2); Update(a, b, x, 2 * k + 2, (l + r) / 2, r); data[k] = Operation((data[2 * k + 1], data[2 * k + 2])); } } [MethodImpl(256)] public T Query(int left, int right) { return Query(left, right + 1, 0, 0, n); } [MethodImpl(256)] private T Query(int a, int b, int k, int l, int r) { Evaluate(k); if (r <= a || b <= l) return E; if (a <= l && r <= b) return data[k]; T vl = Query(a, b, 2 * k + 1, l, (l + r) / 2); T vr = Query(a, b, 2 * k + 2, (l + r) / 2, r); return Operation((vl, vr)); } public override string ToString() { var v = 1 << height; int index = 0; var sb = new StringBuilder(); while (v > 0) { sb.AppendLine($"=== Depth {index} ==="); for (int i = 0; i < n / v; i++) { sb.Append($"{v * i} to {v * i + v - 1} ... "); sb.AppendLine(Query(v * i, v * i + v - 1).ToString()); } v >>= 1; index++; } sb.AppendLine(); return sb.ToString(); } } } namespace Qlibrary { public readonly struct Edge : IComparable>, IEquatable> where T : INumber { public int From { get; } public int To { get; } public T Cost { get; } public Edge(int to, T cost) : this(-1, to, cost) { } public Edge(int from, int to, T cost) { From = from; To = to; Cost = cost; } public static bool operator ==(Edge a, Edge b) => a.Equals(b); public static bool operator !=(Edge a, Edge b) => !(a == b); public int CompareTo(Edge other) => Cost - other.Cost > T.Zero ? 1 : (Cost - other.Cost) < T.Zero ? -1 : 0; public bool Equals(Edge other) => From == other.From && To == other.To; public override bool Equals(object obj) => obj is Edge other && Equals(other); public override int GetHashCode() => HashCode.Combine(From, To); } public class Graph : IEnumerable[]> where T : INumber { private readonly long fromIndex = MathPlus.BigPow(10, 9); private Edge[][] graph; private readonly List>[] tempGraph; private Dictionary[] additionalInfo; public int Count { get; } public int PathCount { get; private set; } public bool IsDirected { get; } public Graph(int n, bool isDirected) { Count = n + 1; tempGraph = Make(Count, () => new List>()); IsDirected = isDirected; } public Graph(int n, int[][] paths, bool isDirected) : this(n, isDirected) { SetPath(paths); } private void SetPath(int[][] paths) { for (int i = 0; i < paths.Length; i++) { var path = paths[i]; int cost = path.Length == 2 ? 1 : path[2]; AddPath(path[0], path[1], T.CreateChecked(cost)); } } public void AddPath(int p, int q, T cost) { PathCount++; tempGraph[p].Add(new Edge(p, q, cost)); if (!IsDirected) tempGraph[q].Add(new Edge(q, p, cost)); } private void SetAdditionalInfo(params int[] v) { additionalInfo = Make(v.Length + 1, () => new Dictionary()); for (int i = 0; i < v.Length - 2; i++) { additionalInfo[i].Add(fromIndex * v[0] + v[1], v[i + 2]); if (!IsDirected) additionalInfo[i].Add(fromIndex * v[1] + v[0], v[i + 2]); } } public void SetMatrix(int[][] paths, int indexed = 1) { for (int i = 0; i < Count; i++) { for (int j = 0; j < Count; j++) { if (paths[i][j] == 0) continue; tempGraph[i + indexed].Add(new Edge(i + indexed, j + indexed, T.CreateChecked(paths[i][j]))); } } } public Edge[][] GetGraph() { if (graph == null) graph = Array.ConvertAll(tempGraph, x => x.ToArray()); return graph; } public Edge[] this[int edge] => GetGraph()[edge]; public IEnumerator[]> GetEnumerator() => GetGraph().AsEnumerable().GetEnumerator(); IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); } } namespace Qlibrary { public static class MathPlus { [MethodImpl(256)] public static long CeilingLong(long value, long div) { if (value >= 0) { return value % div == 0 ? value / div : value / div + 1; } return value / div; } [MethodImpl(256)] public static int Digit(long num, int b) { int digit = 0; while (num > 0) { num /= b; digit++; } return digit; } [MethodImpl(256)] public static int GetNumberCount(long value, int digit, int ary, int searched) { int count = 0; for (int i = 0; i < digit; i++) { if (value % ary == searched) { count++; } value /= 2; } return count; } [MethodImpl(256)] public static long Gcd(long a, long b) { return a > b ? GcdRecursive(a, b) : GcdRecursive(b, a); } [MethodImpl(256)] private static long GcdRecursive(long a, long b) { while (true) { if (b == 0) return a; long a1 = a; a = b; b = a1 % b; } } [MethodImpl(256)] public static (long y, long x, long a) ExtGcd(long a, long b, long x = 0, long y = 0) { if (b == 0) { return (1, 0, a); } (long xx, long yy, long aa) = ExtGcd(b, a % b, y, x); xx -= a / b * yy; return (yy, xx, aa); } [MethodImpl(256)] public static long Inv(long a, long b, long mod) { var dd = ExtGcd(a, mod); if (dd.Item1 < 0) { dd.Item1 += mod; } return (dd.Item1 * b) % mod; } [MethodImpl(256)] public static long Lcm(long a, long b) { checked { return (a / Gcd(a, b)) * b; } } [MethodImpl(256)] public static long Combination(long n, long m) { if (m == 0) return 1; if (n == 0) return 0; return n * Combination(n - 1, m - 1) / m; } [MethodImpl(256)] public static long Permutation(long n, long m) { if (m == 0) return 1; if (n == 0) return 0; long value = 1; for (long i = n; i >= n - m + 1; i--) { value *= i; } return value; } [MethodImpl(256)] public static IEnumerable> GetPermutations(params T[] array) where T : IComparable => GetPermutations(array, 0, array.Length - 1); [MethodImpl(256)] public static IEnumerable> GetPermutations(IEnumerable items) where T : IComparable { var array = items.ToArray(); return GetPermutations(array, 0, array.Length - 1); } [MethodImpl(256)] private static IEnumerable> GetPermutations(IList list, int k, int m) where T : IComparable { if (k == m) { yield return list; } else { for (int i = k; i <= m; i++) { (list[k], list[i]) = (list[i], list[k]); foreach (var perm in GetPermutations(list, k + 1, m)) { yield return perm; } (list[k], list[i]) = (list[i], list[k]); } } } [MethodImpl(256)] public static IEnumerable GetCombinations(IEnumerable items, int k, bool withRepetition = false) { if (k == 0) { yield return new T[] { }; yield break; } if (k == 1) { foreach (var item in items) yield return new T[] { item }; yield break; } IEnumerable enumerable = items as T[] ?? items.ToArray(); foreach (var item in enumerable) { var leftside = new T[] { item }; var unused = withRepetition ? enumerable : enumerable.SkipWhile(e => !e.Equals(item)).Skip(1).ToList(); foreach (var rightside in GetCombinations(unused, k - 1, withRepetition)) { yield return leftside.Concat(rightside).ToArray(); } } } [MethodImpl(256)] public static long BigPow(long baseValue, long pow, long mod = long.MaxValue) { long p = baseValue % mod; long x = 1; long ret = 1; while (true) { if ((pow & x) > 0) { ret = (ret * p) % mod; } x *= 2; if (x > pow) return ret; p = (p * p) % mod; } } [MethodImpl(256)] public static BigInteger MoreBigPow(BigInteger baseValue, BigInteger pow, BigInteger mod) { BigInteger p = baseValue % mod; BigInteger x = 1; BigInteger ret = 1; while (true) { if ((pow & x) > 0) { ret = (ret * p) % mod; } x *= 2; if (x > pow) return ret; p = (p * p) % mod; } } [MethodImpl(256)] public static double ToDegree(double radian) => radian * (180.0 / Math.PI); [MethodImpl(256)] public static long ArithmeticSum(long end) => ArithmeticSum(1, end); [MethodImpl(256)] public static long ArithmeticSum(long start, long end) => (start + end) * (end - start + 1) / 2; [MethodImpl(256)] public static long FloorSum(long n, long m, long a, long b) { long ret = default; if (a >= m) { ret += (n - 1) * n * (a / m) / 2; a %= m; } if (b >= m) { ret += n * (b / m); b %= m; } var y = (a * n + b) / m; if (y == 0) return ret; var x = y * m - b; ret += (n - (x + a - 1) / a) * y; ret += FloorSum(y, a, m, (a - x % a) % a); return ret; } [MethodImpl(256)] public static long FloorSqrt(long value) { var sq = (long)Math.Sqrt(value); while ((sq + 1) * (sq + 1) <= value) { sq++; } while ((sq) * (sq) > value) { sq--; } return sq; } [MethodImpl(256)] public static long CeilingSqrt(long value) { var sq = (long)Math.Sqrt(value); while ((sq) * (sq) < value) { sq++; } while ((sq - 1) * (sq - 1) >= value) { sq--; } return sq; } [MethodImpl(256)] public static long AbsMod(this long l, long mod) { var lm = Math.Abs(l) % mod; if (l < 0) { lm = (mod - lm); } return lm; } } } namespace Qlibrary { public class HeavyLightDecomposition where T : INumber { [MethodImpl(256)] private void DfsForSize(int cur) { Size[cur] = 1; for (int i = 0; i < Graph[cur].Length; i++) { var dst = Graph[cur][i]; if (dst.To == Parent[cur]) { if (Graph[cur].Length >= 2 && dst.To == Graph[cur][0].To) { (Graph[cur][0], Graph[cur][1]) = (Graph[cur][1], Graph[cur][0]); dst = Graph[cur][0]; } else { continue; } } Depth[dst.To] = Depth[cur] + 1; Parent[dst.To] = cur; DfsForSize(dst.To); Size[cur] += Size[dst.To]; if (Size[dst.To] > Size[Graph[cur][0].To]) { (Graph[cur][0], Graph[cur][i]) = (Graph[cur][i], Graph[cur][0]); } } } public List<(int, int)> Tour { get; } = new(); [MethodImpl(256)] private void DfsForHld(int cur) { Down[cur] = id++; Tour.Add((Parent[cur], cur)); foreach (var dst in Graph[cur].Where(dst => dst.To != Parent[cur])) { Next[dst.To] = dst.To == Graph[cur][0].To ? Next[cur] : dst.To; DfsForHld(dst.To); } Up[cur] = id; } [MethodImpl(256)] private List<(int, int)> Ascend(int u, int v) { List<(int, int)> res = new List<(int, int)>(); while (Next[u] != Next[v]) { res.Add((Down[u], Down[Next[u]])); u = Parent[Next[u]]; } if (u != v) res.Add((Down[u], Down[v] + 1)); return res; } [MethodImpl(256)] private List<(int, int)> Descend(int u, int v) { if (u == v) return new List<(int, int)>(); if (Next[u] == Next[v]) return new List<(int, int)>() { (Down[u] + 1, Down[v]) }; var res = Descend(u, Parent[Next[v]]); res.Add((Down[Next[v]], Down[v])); return res; } protected readonly Graph Graph; private int id; public int[] Depth { get; } public int[] Size { get; } protected readonly int[] Down; protected readonly int[] Up; protected readonly int[] Next; protected readonly int[] Parent; public HeavyLightDecomposition(Graph graph, int root = 1) { this.Graph = graph; id = 0; Size = new int[graph.Count]; Depth = new int[graph.Count]; Down = new int[graph.Count]; Up = new int[graph.Count]; Next = new int[graph.Count]; Parent = new int[graph.Count]; Down.Init(-1); Up.Init(-1); Next.Init(root); Parent.Init(root); DfsForSize(root); DfsForHld(root); } public void Build(int root) { DfsForSize(root); DfsForHld(root); } public (int In, int Out) Index(int i) { return (Down[i], Up[i]); } [MethodImpl(256)] public void QueryPath(int u, int v, bool vertex, Action f) { int l = GetLca(u, v); foreach (var(a, b)in Ascend(u, l)) { int s = a + 1; if (s > b) { f(b, s); } else { f(s, b); } } if (vertex) f(Down[l], Down[l] + 1); foreach (var(a, b)in Descend(l, v)) { int t = b + 1; if (a > t) { f(t, a); } else { f(a, t); } } } public void QueryPathNonCommutative(int u, int v, bool vertex, Action f) { int l = GetLca(u, v); foreach (var(a, b)in Ascend(u, l)) f(a + 1, b); if (vertex) f(Down[l], Down[l] + 1); foreach (var(a, b)in Descend(l, v)) f(a, b + 1); } public void QuerySubtree(int u, bool vertex, Action f) { f(Down[u] + (vertex ? 0 : 1), Up[u]); } public int GetLca(int a, int b) { while (Next[a] != Next[b]) { if (Down[a] < Down[b]) (a, b) = (b, a); a = Parent[Next[a]]; } return Depth[a] < Depth[b] ? a : b; } public int Distance(int a, int b) { return Depth[a] + Depth[b] - Depth[GetLca(a, b)] * 2; } }; } namespace Qlibrary { public class LazyHeavyLightTree : HeavyLightDecomposition where T : INumber { private bool isInitForVertex; public LazySegmentTree vertexSegTree; private int[] vertexToIndex; public Func<(T A, T B), T> OperationVertex { get => vertexSegTree.Operation; set => vertexSegTree.Operation = value; } public Func<(T Current, T Lazy, int length), T> MappingVertex { set => vertexSegTree.Mapping = value; } public Func<(T F, T G), T> CompositionVertex { set => vertexSegTree.Composition = value; } public LazyHeavyLightTree(Graph graph, int root = 1) : base(graph, root) { } [MethodImpl(256)] public void InitForVertex(T firstValue = default) { isInitForVertex = true; vertexToIndex = new int[Graph.Count]; for (int i = 0; i < Graph.Count; i++) { var index = Index(i); if (index.In == -1) continue; vertexToIndex[i] = index.In; } vertexSegTree = new LazySegmentTree(Graph.Count, firstValue); } [MethodImpl(256)] public void BuildForVertex(T[] values) { var ar = new int[Graph.Count]; for (int i = 0; i < Graph.Count - 1; i++) { ar[vertexToIndex[i]] = i; } vertexSegTree.Build(i => values[ar[i]]); } [MethodImpl(256)] public void UpdateVertexOfPath(int u, int v, T value) { Debug.Assert(isInitForVertex); QueryPath(u, v, true, (i1, i2) => vertexSegTree.Update(i1, i2 - 1, value)); } [MethodImpl(256)] public T QueryForVertexesOfPath(int u, int v) { Debug.Assert(isInitForVertex); T value = T.Zero; QueryPath(u, v, true, (i1, i2) => value = OperationVertex((value, vertexSegTree.Query(i1, i2 - 1)))); return value; } } } namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}} #endregion Expanded by https://github.com/kzrnm/SourceExpander