結果

問題 No.399 動的な領主
ユーザー QlionQlion
提出日時 2024-07-04 23:58:37
言語 C#
(.NET 8.0.203)
結果
TLE  
実行時間 -
コード長 22,008 bytes
コンパイル時間 7,939 ms
コンパイル使用メモリ 167,192 KB
実行使用メモリ 262,100 KB
最終ジャッジ日時 2024-07-04 23:59:12
合計ジャッジ時間 31,284 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 68 ms
29,440 KB
testcase_01 AC 67 ms
29,432 KB
testcase_02 AC 72 ms
29,804 KB
testcase_03 AC 66 ms
29,824 KB
testcase_04 AC 78 ms
33,536 KB
testcase_05 AC 256 ms
60,732 KB
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 AC 84 ms
36,224 KB
testcase_11 AC 212 ms
60,980 KB
testcase_12 AC 1,727 ms
97,056 KB
testcase_13 AC 1,667 ms
96,812 KB
testcase_14 AC 1,011 ms
129,712 KB
testcase_15 AC 1,128 ms
129,840 KB
testcase_16 AC 1,417 ms
110,964 KB
testcase_17 TLE -
testcase_18 TLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (89 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

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<long>(n, uv, false);
                var ls = new LazyHeavyLightTree<long>(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<T>(int n, Func<T> creator) => Enumerable.Repeat(0, n).Select(_ => creator()).ToArray(); [MethodImpl(256)] public static (T, T) SorTuple<T>(T a, T b) where T : IComparable<T> => a.CompareTo(b) < 0 ? (a, b) : (b, a); [MethodImpl(256)] public static (T, T) SorTuple<T>((T, T) t) where T : IComparable<T> => 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<T>() where T : INumberBase<T> { 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>(T v1, T v2) where T : INumber<T> => v1 <= v2 ? v1 : v2; [MethodImpl(256)] public static T GMax<T>(T v1, T v2) where T : INumber<T> => v1 >= v2 ? v1 : v2; private static T[, ] Rotate90<T>(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<T>(this T[, ] self, int count) { for (int i = 0; i < count; i++) { self = self.Rotate90(); }  return self; }  public static T[, ] Rotate90<T>(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<T1, T2>(this Dictionary<T1, T2> self, T1 key, Action<T2> action) where T2 : new() { if (!self.ContainsKey(key)) { self.Add(key, new T2()); }  action(self[key]); }  public static void Init<T>(this T[] array, T value) => Array.Fill(array, value); public static void Init<T>(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<T>(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<T> { 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<int, T> 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<T> : IComparable<Edge<T>>, IEquatable<Edge<T>> where T : INumber<T> { 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<T> a, Edge<T> b) => a.Equals(b); public static bool operator !=(Edge<T> a, Edge<T> b) => !(a == b); public int CompareTo(Edge<T> other) => Cost - other.Cost > T.Zero ? 1 : (Cost - other.Cost) < T.Zero ? -1 : 0; public bool Equals(Edge<T> other) => From == other.From && To == other.To; public override bool Equals(object obj) => obj is Edge<T> other && Equals(other); public override int GetHashCode() => HashCode.Combine(From, To); }  public class Graph<T> : IEnumerable<Edge<T>[]> where T : INumber<T> { private readonly long fromIndex = MathPlus.BigPow(10, 9); private Edge<T>[][] graph; private readonly List<Edge<T>>[] tempGraph; private Dictionary<long, long>[] 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<Edge<T>>()); 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<T>(p, q, cost)); if (!IsDirected) tempGraph[q].Add(new Edge<T>(q, p, cost)); }  private void SetAdditionalInfo(params int[] v) { additionalInfo = Make(v.Length + 1, () => new Dictionary<long, long>()); 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<T>(i + indexed, j + indexed, T.CreateChecked(paths[i][j]))); } } }  public Edge<T>[][] GetGraph() { if (graph == null) graph = Array.ConvertAll(tempGraph, x => x.ToArray()); return graph; }  public Edge<T>[] this[int edge] => GetGraph()[edge]; public IEnumerator<Edge<T>[]> 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<IEnumerable<T>> GetPermutations<T>(params T[] array) where T : IComparable => GetPermutations(array, 0, array.Length - 1); [MethodImpl(256)] public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> items) where T : IComparable { var array = items.ToArray(); return GetPermutations(array, 0, array.Length - 1); }  [MethodImpl(256)] private static IEnumerable<IEnumerable<T>> GetPermutations<T>(IList<T> 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<T[]> GetCombinations<T>(IEnumerable<T> 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<T> 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<T> where T : INumber<T> { [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<T> 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<T> 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<int, int> 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<int, int> 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<int, int> 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<T> : HeavyLightDecomposition<T> where T : INumber<T> { private bool isInitForVertex; public LazySegmentTree<T> 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<T> 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<T>(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
0