結果
| 問題 | No.2337 Equidistant |
| ユーザー |
 yupiteru_kun
|
| 提出日時 | 2023-06-02 21:38:55 |
| 言語 | C# (.NET 8.0.203) |
| 結果 |
AC
|
| 実行時間 | 3,541 ms / 4,000 ms |
| コード長 | 39,883 bytes |
| コンパイル時間 | 9,455 ms |
| コンパイル使用メモリ | 167,572 KB |
| 実行使用メモリ | 232,916 KB |
| 最終ジャッジ日時 | 2024-06-08 22:32:16 |
| 合計ジャッジ時間 | 58,496 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 73 ms
29,824 KB |
| testcase_01 | AC | 70 ms
29,696 KB |
| testcase_02 | AC | 72 ms
29,824 KB |
| testcase_03 | AC | 76 ms
29,952 KB |
| testcase_04 | AC | 74 ms
29,824 KB |
| testcase_05 | AC | 74 ms
29,696 KB |
| testcase_06 | AC | 105 ms
35,072 KB |
| testcase_07 | AC | 102 ms
34,944 KB |
| testcase_08 | AC | 102 ms
34,816 KB |
| testcase_09 | AC | 101 ms
34,944 KB |
| testcase_10 | AC | 104 ms
35,072 KB |
| testcase_11 | AC | 2,618 ms
227,348 KB |
| testcase_12 | AC | 2,416 ms
227,140 KB |
| testcase_13 | AC | 2,419 ms
227,144 KB |
| testcase_14 | AC | 2,387 ms
227,200 KB |
| testcase_15 | AC | 2,424 ms
227,276 KB |
| testcase_16 | AC | 2,463 ms
227,160 KB |
| testcase_17 | AC | 2,418 ms
227,196 KB |
| testcase_18 | AC | 2,395 ms
227,080 KB |
| testcase_19 | AC | 2,430 ms
227,196 KB |
| testcase_20 | AC | 2,392 ms
227,368 KB |
| testcase_21 | AC | 2,878 ms
207,724 KB |
| testcase_22 | AC | 2,129 ms
232,108 KB |
| testcase_23 | AC | 2,195 ms
232,468 KB |
| testcase_24 | AC | 3,541 ms
207,804 KB |
| testcase_25 | AC | 2,239 ms
232,776 KB |
| testcase_26 | AC | 3,434 ms
207,944 KB |
| testcase_27 | AC | 2,356 ms
232,916 KB |
| testcase_28 | AC | 2,314 ms
232,888 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (91 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/
ソースコード
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using static System.Math;
using System.Text;
using System.Threading;
using System.Globalization;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using Library;
namespace Program
{
public static class ProblemD
{
static bool SAIKI = false;
static public int numberOfRandomCases = 0;
static public void MakeTestCase(List<string> _input, List<string> _output, ref Func<string[], bool> _outputChecker)
{
}
static public void Solve()
{
var N = NN;
var Q = NN;
var AB = Repeat(0, N - 1).Select(_ => new { A = NN - 1, B = NN - 1 }).ToArray();
var ST = Repeat(0, Q).Select(_ => new { S = NN - 1, T = NN - 1 }).ToArray();
var tree = new LIB_Tree(N);
foreach (var item in AB)
{
tree.AddPath(item.A, item.B);
}
var dp = tree.LIB_ReRooting<long>()
.VertexToValue(e => 1)
.MergeSubtrees((s, t) => s + t)
.MergeVertexAndSubtree((v, s) => v + s)
.Build();
var containsVtx = new bool[N];
var deq = new LIB_Deque<long>();
var mo = tree.LIB_OfflinePathQuery(0).SetAddRightEdgeMethod((a, b) =>
{
var idx = a;
if (idx == -1 || containsVtx[idx]) idx = b;
deq.PushBack(idx);
containsVtx[idx] = true;
}).SetAddLeftEdgeMethod((a, b) =>
{
var idx = a;
if (idx == -1 || containsVtx[idx]) idx = b;
deq.PushFront(idx);
containsVtx[idx] = true;
}).SetDeleteRightEdgeMethod((a, b) =>
{
containsVtx[deq.PopBack()] = false;
}).SetDeleteLeftEdgeMethod((a, b) =>
{
containsVtx[deq.PopFront()] = false;
});
foreach (var item in ST)
{
mo.AddQuery(item.S, item.T);
}
var answer = new long[Q];
mo.SetChecker(ansIdx =>
{
if (deq.Count % 2 == 0) answer[ansIdx] = 0;
else
{
var left = deq[deq.Count / 2 - 1];
var center = deq[deq.Count / 2];
var right = deq[deq.Count / 2 + 1];
answer[ansIdx] = N - dp[left, center] - dp[right, center];
}
});
mo.Execute();
foreach (var item in answer)
{
Console.WriteLine(item);
}
}
class Printer : StreamWriter
{
public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { base.AutoFlush = false; }
public Printer(Stream stream, Encoding encoding) : base(stream, encoding) { base.AutoFlush = false; }
}
static LIB_FastIO fastio = new LIB_FastIODebug();
static string[] args;
static public void Main(string[] args_t) { args = args_t; if (args_t.Length == 0) { fastio = new LIB_FastIO(); Console.SetOut(new Printer(Console.OpenStandardOutput())); } if (SAIKI) { var t = new Thread(Solve, 134217728); t.Start(); t.Join(); } else Solve(); Console.Out.Flush(); }
static long NN => fastio.Long();
static double ND => fastio.Double();
static string NS => fastio.Scan();
static long[] NNList(long N) => Repeat(0, N).Select(_ => NN).ToArray();
static double[] NDList(long N) => Repeat(0, N).Select(_ => ND).ToArray();
static string[] NSList(long N) => Repeat(0, N).Select(_ => NS).ToArray();
static long Count<T>(this IEnumerable<T> x, Func<T, bool> pred) => Enumerable.Count(x, pred);
static IEnumerable<T> Repeat<T>(T v, long n) => Enumerable.Repeat<T>(v, (int)n);
static IEnumerable<int> Range(long s, long c) => Enumerable.Range((int)s, (int)c);
static IOrderedEnumerable<T> OrderByRand<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x, _ => xorshift);
static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x.OrderByRand(), e => e);
static IOrderedEnumerable<T1> OrderBy<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderBy(x.OrderByRand(), selector);
static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x) => Enumerable.OrderByDescending(x.OrderByRand(), e => e);
static IOrderedEnumerable<T1> OrderByDescending<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderByDescending(x.OrderByRand(), selector);
static IOrderedEnumerable<string> OrderBy(this IEnumerable<string> x) => x.OrderByRand().OrderBy(e => e, StringComparer.OrdinalIgnoreCase);
static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderBy(selector, StringComparer.OrdinalIgnoreCase);
static IOrderedEnumerable<string> OrderByDescending(this IEnumerable<string> x) => x.OrderByRand().OrderByDescending(e => e, StringComparer.OrdinalIgnoreCase);
static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderByDescending(selector, StringComparer.OrdinalIgnoreCase);
static string Join<T>(this IEnumerable<T> x, string separator = "") => string.Join(separator, x);
static uint xorshift { get { _xsi.MoveNext(); return _xsi.Current; } }
static IEnumerator<uint> _xsi = _xsc();
static IEnumerator<uint> _xsc() { uint x = 123456789, y = 362436069, z = 521288629, w = (uint)(DateTime.Now.Ticks & 0xffffffff); while (true) { var t = x ^ (x << 11); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); yield return w; } }
static bool Chmax<T>(this ref T lhs, T rhs) where T : struct, IComparable<T> { if (lhs.CompareTo(rhs) < 0) { lhs = rhs; return true; } return false; }
static bool Chmin<T>(this ref T lhs, T rhs) where T : struct, IComparable<T> { if (lhs.CompareTo(rhs) > 0) { lhs = rhs; return true; } return false; }
static void Fill<T>(this T[] array, T value) => array.AsSpan().Fill(value);
static void Fill<T>(this T[,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0], array.Length).Fill(value);
static void Fill<T>(this T[,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0], array.Length).Fill(value);
static void Fill<T>(this T[,,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0, 0], array.Length).Fill(value);
}
}
namespace Library {
class LIB_SlidingWindowAggregation<T>
{
T[][] list;
T[][] agg;
int[] size;
Func<T, T, T> fun;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_SlidingWindowAggregation(IEnumerable<T> ary, Func<T, T, T> f)
{
list = new T[2][]; agg = new T[2][]; size = new int[2];
fun = f;
list[0] = new T[16]; agg[0] = new T[16]; size[0] = 0;
if (ary.Any())
{
var temp = ary.ToArray();
size[1] = temp.Length;
list[1] = new T[size[1]];
agg[1] = new T[size[1]];
for (var i = 0; i < list[1].Length; i++)
{
list[1][i] = temp[i];
if (i == 0) agg[1][i] = temp[i];
else agg[1][i] = fun(agg[1][i - 1], temp[i]);
}
}
else
{
list[1] = new T[16]; agg[1] = new T[16]; size[1] = 0;
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_SlidingWindowAggregation(Func<T, T, T> f) : this(new T[0], f) { }
public int Count => size[0] + size[1];
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Clear()
{
size[0] = size[1] = 0;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
void Push(int lista, T val)
{
if (list[lista].Length == size[lista])
{
var newAry = new T[size[lista] * 2];
var newAgg = new T[size[lista] * 2];
Array.Copy(list[lista], newAry, size[lista]);
Array.Copy(agg[lista], newAgg, size[lista]);
list[lista] = newAry;
agg[lista] = newAgg;
}
if (size[lista] == 0) agg[lista][0] = val;
else if (lista == 0) agg[lista][size[lista]] = fun(val, agg[lista][size[lista] - 1]);
else agg[lista][size[lista]] = fun(agg[lista][size[lista] - 1], val);
list[lista][size[lista]++] = val;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void PushBack(T val) => Push(1, val);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void PushFront(T val) => Push(0, val);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
T Pop(int lista)
{
var listb = 1 - lista;
if (size[lista] == 0)
{
if (size[listb] == 0) throw new Exception();
var mid = (size[listb] - 1) / 2;
if (list[lista].Length <= mid)
{
list[lista] = new T[mid + 1];
agg[lista] = new T[mid + 1];
}
size[lista] = 0;
for (var i = mid; i >= 0; i--)
{
if (size[lista] == 0) agg[lista][size[lista]] = list[listb][i];
else if (lista == 0) agg[lista][size[lista]] = fun(list[listb][i], agg[lista][size[lista] - 1]);
else agg[lista][size[lista]] = fun(agg[lista][size[lista] - 1], list[listb][i]);
list[lista][size[lista]++] = list[listb][i];
}
for (var i = mid + 1; i < size[listb]; i++)
{
var idx = i - mid - 1;
if (idx == 0) agg[listb][idx] = list[listb][i];
else if (lista == 0) agg[listb][idx] = fun(list[listb][i], agg[listb][idx - 1]);
else agg[listb][idx] = fun(agg[listb][idx - 1], list[listb][i]);
list[listb][idx] = list[listb][i];
}
size[listb] -= size[lista];
}
return list[lista][--size[lista]];
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public T PopBack() => Pop(1);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public T PopFront() => Pop(0);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public T Aggregate()
{
if (size[0] == 0 && size[1] == 0) throw new Exception();
else if (size[1] == 0) return agg[0][size[0] - 1];
else if (size[0] == 0) return agg[1][size[1] - 1];
else return fun(agg[0][size[0] - 1], agg[1][size[1] - 1]);
}
}
// copy key class LIB_OfflinePathQuery
partial class /* not copy key */ LIB_Tree
{
readonly struct Query
{
public readonly int idx;
public readonly int l;
public readonly int r;
public Query(int idx, int l, int r) { this.idx = idx; this.l = l; this.r = r; }
}
readonly struct Edge
{
public readonly int idx;
public readonly int a;
public readonly int b;
public Edge(int a, int b, Dictionary<long, int> table)
{
var key = 0L;
if (a > b) key = ((long)a << 30) | (long)b;
else key = ((long)b << 30) | (long)a;
if (!table.ContainsKey(key))
{
this.idx = table.Count;
table[key] = this.idx;
}
else
{
this.idx = table[key];
}
this.a = a;
this.b = b;
}
}
public CPathQuery LIB_OfflinePathQuery(long root) => new CPathQuery((int)root, this);
public class CPathQuery
{
LIB_Tree tree;
Edge[] array;
int[] vtxToArrayIndex;
int root;
List<Query> queries;
int maxL;
int maxR;
int minL;
int minR;
int queryNum;
(int nextL, int nextR)[] warpWayToL;
(int nextL, int nextR)[] warpWayToR;
Action<int, int> addRightEdge;
Action<int, int> addLeftEdge;
Action<int, int> deleteRightEdge;
Action<int, int> deleteLeftEdge;
Action<int> checker;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public CPathQuery(int root, LIB_Tree tree)
{
maxL = maxR = int.MinValue;
minL = minR = int.MaxValue;
queryNum = 0;
queries = new List<Query>();
addRightEdge = addLeftEdge = deleteRightEdge = deleteLeftEdge = (e1, e2) => { };
checker = e => { };
var table = new Dictionary<long, int>();
this.root = root;
this.tree = tree;
array = new Edge[tree.N * 2 - 1];
var tour = tree.EulerTour(root);
vtxToArrayIndex = new int[tree.N];
for (var i = 0; i < tour.Length - 1; ++i)
{
if (tour[i].direction == 1)
{
array[i] = new Edge((int)tour[i].parent, (int)tour[i].node, table);
vtxToArrayIndex[tour[i].node] = i;
}
else
{
array[i] = new Edge((int)tour[i].node, (int)tour[i].parent, table);
}
}
warpWayToL = new (int nextL, int nextR)[tree.N * 2];
warpWayToR = new (int nextL, int nextR)[tree.N * 2];
var aikataA = new int[tree.N];
for (var i = 1; i < array.Length; ++i)
{
aikataA[array[i].idx] ^= i;
warpWayToL[i].nextR = array.Length;
warpWayToR[i].nextR = array.Length;
}
for (var i = 1; i < array.Length; ++i)
{
var aikata = aikataA[array[i].idx] ^ i;
if (aikata < i)
{
warpWayToR[aikata - 1].nextR = i;
warpWayToR[i].nextL = aikata - 1;
}
else
{
warpWayToL[i].nextR = aikata + 1;
warpWayToL[aikata + 1].nextL = i;
}
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public int AddQuery(long vtx1, long vtx2)
{
var l = vtxToArrayIndex[vtx1];
var r = vtxToArrayIndex[vtx2];
if (r < l) { var t = l; l = r; r = t; }
if (maxL < l) maxL = l;
if (minL > l) minL = l;
if (maxR < r) maxR = r;
if (minR > r) minR = r;
queries.Add(new Query(queryNum, l + 1, r + 1));
return queryNum++;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
/// <summary>
/// 指定した 辺 を追加するメソッドを設定
/// (from, to)
/// </summary>
public CPathQuery SetAddEdgeMethod(Action<int, int> act)
{
addRightEdge = addLeftEdge = act;
return this;
}
public CPathQuery SetAddRightEdgeMethod(Action<int, int> act)
{
addRightEdge = act;
return this;
}
public CPathQuery SetAddLeftEdgeMethod(Action<int, int> act)
{
addLeftEdge = act;
return this;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
/// <summary>
/// 指定した 辺 を削除するメソッドを設定
/// (from, to)
/// </summary>
public CPathQuery SetDeleteEdgeMethod(Action<int, int> act)
{
deleteRightEdge = deleteLeftEdge = act;
return this;
}
public CPathQuery SetDeleteRightEdgeMethod(Action<int, int> act)
{
deleteRightEdge = act;
return this;
}
public CPathQuery SetDeleteLeftEdgeMethod(Action<int, int> act)
{
deleteLeftEdge = act;
return this;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
/// <summary>
/// 指定した クエリindex の答えを処理するメソッドを設定
/// </summary>
public CPathQuery SetChecker(Action<int> act)
{
checker = act;
return this;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Execute()
{
Query[] sorted;
if (maxL - minL > maxR - minR)
{
var blockSize = Max(1, (int)(1.7320508 * (maxR - minR + 1) / Sqrt(2 * queryNum)));
sorted = queries.OrderBy(e => (e.r - minR + 1) / blockSize).ThenBy(e => (((e.r - minR + 1) / blockSize & 1) == 1) ? -e.l : e.l).ToArray();
}
else
{
var blockSize = Max(1, (int)(1.7320508 * (maxL - minL + 1) / Sqrt(2 * queryNum)));
sorted = queries.OrderBy(e => (e.l - minL + 1) / blockSize).ThenBy(e => (((e.l - minL + 1) / blockSize & 1) == 1) ? -e.r : e.r).ToArray();
}
var lidx = 1;
var ridx = 1;
var isOdd = new bool[tree.N];
ref var isOddRef = ref isOdd[0];
ref var arrayRef = ref array[0];
ref var warpWayToLRef = ref warpWayToL[0];
ref var warpWayToRRef = ref warpWayToR[0];
addRightEdge(-1, root);
foreach (var item in sorted)
{
while (true)
{
while (item.l <= Unsafe.Add(ref warpWayToLRef, lidx).nextL) lidx = Unsafe.Add(ref warpWayToLRef, lidx).nextL;
if (item.l >= lidx) break;
var edge = Unsafe.Add(ref arrayRef, --lidx);
if (Unsafe.Add(ref isOddRef, edge.idx)) deleteLeftEdge(edge.a, edge.b);
else addLeftEdge(edge.b, edge.a);
Unsafe.Add(ref isOddRef, edge.idx) = !Unsafe.Add(ref isOddRef, edge.idx);
}
while (true)
{
while (Unsafe.Add(ref warpWayToRRef, ridx - 1).nextR + 1 <= item.r) ridx = Unsafe.Add(ref warpWayToRRef, ridx - 1).nextR + 1;
if (ridx >= item.r) break;
var edge = Unsafe.Add(ref arrayRef, ridx++);
if (Unsafe.Add(ref isOddRef, edge.idx)) deleteRightEdge(edge.b, edge.a);
else addRightEdge(edge.a, edge.b);
Unsafe.Add(ref isOddRef, edge.idx) = !Unsafe.Add(ref isOddRef, edge.idx);
}
while (true)
{
while (Unsafe.Add(ref warpWayToLRef, lidx).nextR <= item.l) lidx = Unsafe.Add(ref warpWayToLRef, lidx).nextR;
if (lidx >= item.l) break;
var edge = Unsafe.Add(ref arrayRef, lidx++);
if (Unsafe.Add(ref isOddRef, edge.idx)) deleteLeftEdge(edge.b, edge.a);
else addLeftEdge(edge.a, edge.b);
Unsafe.Add(ref isOddRef, edge.idx) = !Unsafe.Add(ref isOddRef, edge.idx);
}
while (true)
{
while (item.r <= Unsafe.Add(ref warpWayToRRef, ridx - 1).nextL + 1) ridx = Unsafe.Add(ref warpWayToRRef, ridx - 1).nextL + 1;
if (item.r >= ridx) break;
var edge = Unsafe.Add(ref arrayRef, --ridx);
if (Unsafe.Add(ref isOddRef, edge.idx)) deleteRightEdge(edge.a, edge.b);
else addRightEdge(edge.b, edge.a);
Unsafe.Add(ref isOddRef, edge.idx) = !Unsafe.Add(ref isOddRef, edge.idx);
}
checker(item.idx);
}
}
}
}
class LIB_Deque<T>
{
T[] array;
int front, cap;
public int Count;
public T this[long i]
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
get { return array[GetIndex((int)i)]; }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
set { array[GetIndex((int)i)] = value; }
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_Deque(long cap = 16)
{
array = new T[this.cap = (int)cap];
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
int GetIndex(int i)
{
if (i >= cap) throw new Exception();
var r = front + i;
return r >= cap ? r - cap : r;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void PushFront(T x)
{
if (Count == cap) Extend();
if (--front < 0) front += array.Length;
array[front] = x;
++Count;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public T PopFront()
{
if (Count-- == 0) throw new Exception();
var r = array[front++];
if (front >= cap) front -= cap;
return r;
}
public T Front => array[front];
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void PushBack(T x)
{
if (Count == cap) Extend();
var i = front + Count++;
array[i >= cap ? i - cap : i] = x;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public T PopBack()
{
if (Count == 0) throw new Exception();
return array[GetIndex(--Count)];
}
public T Back => array[GetIndex(Count - 1)];
[MethodImpl(MethodImplOptions.AggressiveInlining)]
void Extend()
{
T[] nb = new T[cap << 1];
if (front > cap - Count)
{
var l = array.Length - front; Array.Copy(array, front, nb, 0, l);
Array.Copy(array, 0, nb, l, Count - l);
}
else Array.Copy(array, front, nb, 0, Count);
array = nb; front = 0; cap <<= 1;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Insert(long i, T x)
{
if (i > Count) throw new Exception();
this.PushFront(x);
for (int j = 0; j < i; j++) this[j] = this[j + 1];
this[i] = x;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public T RemoveAt(long i)
{
if (i < 0 || i >= Count) throw new Exception();
var r = this[i];
for (var j = i; j > 0; j--) this[j] = this[j - 1];
this.PopFront();
return r;
}
}
// copy key class LIB_ReRooting
partial class /* not copy key */ LIB_Tree
{
/// <summary>
/// 全方位木DP
/// </summary>
/// <returns>2次元配列[node, parent]の部分木のDP値。parent=-1はnodeをルートとした木の値</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public CReRooting<T> LIB_ReRooting<T>() => new CReRooting<T>(this);
public class CReRooting<T>
{
LIB_Tree tree;
Dictionary<int, T>[] dp;
Func<T, T, T> f;
Func<long, T> g;
Func<long, long, T, T> g2;
Func<T, T, T> h;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public CReRooting(LIB_Tree tree)
{
this.tree = tree;
dp = Enumerable.Repeat(0, tree.N).Select(_ => new Dictionary<int, T>()).ToArray();
f = (x, y) => throw new NotImplementedException();
g = v => throw new NotImplementedException();
g2 = (r, p, v) => v;
h = (v, t) => t;
}
public T this[long vtx, long parent]
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
get { return dp[vtx][(int)parent]; }
}
/// <summary>
/// 部分木と部分木のマージ(subtree, subtree)するメソッドを設定
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public CReRooting<T> MergeSubtrees(Func<T, T, T> mergeSubTrees) { f = mergeSubTrees; return this; }
/// <summary>
/// 頂点番号から値を取得するメソッドを設定
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public CReRooting<T> VertexToValue(Func<long, T> idxToVal) { g = idxToVal; return this; }
/// <summary>
/// 頂点番号(root, parent)で表す辺とrootをルートとする部分木をマージするメソッドを設定
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public CReRooting<T> MergeEdgeAndSubtree(Func<long, long, T, T> mergeEdgeAndSubtree) { g2 = mergeEdgeAndSubtree; return this; }
/// <summary>
/// 頂点と部分木の結果をマージ(vertex, subtrees)するメソッドを設定
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public CReRooting<T> MergeVertexAndSubtree(Func<T, T, T> mergeVertexAndSubtree) { h = mergeVertexAndSubtree; return this; }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public CReRooting<T> Build()
{
var done = new bool[tree.N];
Action<long, long, T> upd = (vtx, rt, val) =>
{
if (vtx == -1) return;
if (done[vtx]) dp[vtx][-1] = f(dp[vtx][-1], g2(rt, vtx, val));
else dp[vtx][-1] = g2(rt, vtx, val);
done[vtx] = true;
};
foreach (var item in tree.BFSFromLeaf(0))
{
var ary = tree.path[item.node].Where(e => e != item.parent).ToArray();
var val = g(item.node);
if (ary.Length > 0)
{
var acc = g2(ary[0], item.node, dp[ary[0]][(int)item.node]);
foreach (var item2 in ary.Skip(1)) acc = f(acc, g2(item2, item.node, dp[item2][(int)item.node]));
val = h(val, acc);
}
upd(item.parent, item.node, dp[item.node][(int)item.parent] = val);
}
var swag = new LIB_SlidingWindowAggregation<T>(f);
Action<int, int> process = (node, parent) =>
{
var val = g(node);
if (tree.path[node].Count == 1)
{
var x = tree.path[node][0];
if (x != parent) upd(x, node, dp[node][x] = val);
}
else if (tree.path[node].Count == 2)
{
var x = tree.path[node][0]; var y = tree.path[node][1];
if (x != parent) upd(x, node, dp[node][x] = h(val, g2(y, node, dp[y][node])));
if (y != parent) upd(y, node, dp[node][y] = h(val, g2(x, node, dp[x][node])));
}
else if (tree.path[node].Count == 3)
{
var x = tree.path[node][0]; var y = tree.path[node][1]; var z = tree.path[node][2];
if (x != parent) upd(x, node, dp[node][x] = h(val, f(g2(y, node, dp[y][node]), g2(z, node, dp[z][node]))));
if (y != parent) upd(y, node, dp[node][y] = h(val, f(g2(x, node, dp[x][node]), g2(z, node, dp[z][node]))));
if (z != parent) upd(z, node, dp[node][z] = h(val, f(g2(x, node, dp[x][node]), g2(y, node, dp[y][node]))));
}
else if (tree.path[node].Count == 4)
{
var x = tree.path[node][0]; var y = tree.path[node][1]; var z = tree.path[node][2]; var w = tree.path[node][3];
var xy = f(g2(x, node, dp[x][node]), g2(y, node, dp[y][node]));
var zw = f(g2(z, node, dp[z][node]), g2(w, node, dp[w][node]));
if (x != parent) upd(x, node, dp[node][x] = h(val, f(g2(y, node, dp[y][node]), zw)));
if (y != parent) upd(y, node, dp[node][y] = h(val, f(g2(x, node, dp[x][node]), zw)));
if (z != parent) upd(z, node, dp[node][z] = h(val, f(xy, g2(w, node, dp[w][node]))));
if (w != parent) upd(w, node, dp[node][w] = h(val, f(xy, g2(z, node, dp[z][node]))));
}
else
{
swag.Clear();
var pre = new T[tree.path[node].Count];
for (var i = 0; i < pre.Length; ++i) swag.PushBack(pre[i] = g2(tree.path[node][i], node, dp[tree.path[node][i]][node]));
for (var i = 0; i < pre.Length; ++i)
{
var item2 = tree.path[node][i];
swag.PopFront();
if (item2 != parent) upd(item2, node, dp[node][item2] = h(val, swag.Aggregate()));
swag.PushBack(pre[i]);
}
}
};
foreach (var item in tree.BFSFromRoot(0)) process((int)item.node, (int)item.parent);
for (var i = 1; i < tree.N; i++) dp[i][-1] = done[i] ? h(g(i), dp[i][-1]) : g(i);
return this;
}
}
}
class LIB_FastIO
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_FastIO() { str = Console.OpenStandardInput(); }
readonly Stream str;
readonly byte[] buf = new byte[2048];
int len, ptr;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
byte read()
{
if (ptr >= len)
{
ptr = 0;
if ((len = str.Read(buf, 0, 2048)) <= 0)
{
return 0;
}
}
return buf[ptr++];
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
char Char()
{
byte b = 0;
do b = read();
while (b < 33 || 126 < b);
return (char)b;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
virtual public string Scan()
{
var sb = new StringBuilder();
for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
sb.Append(b);
return sb.ToString();
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
virtual public long Long()
{
long ret = 0; byte b = 0; var 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 << 3) + (ret << 1) + b - '0';
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
virtual public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); }
}
class LIB_FastIODebug : LIB_FastIO
{
Queue<string> param = new Queue<string>();
[MethodImpl(MethodImplOptions.AggressiveInlining)]
string NextString() { if (param.Count == 0) foreach (var item in Console.ReadLine().Split(' ')) param.Enqueue(item); return param.Dequeue(); }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_FastIODebug() { }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public override string Scan() => NextString();
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public override long Long() => long.Parse(NextString());
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public override double Double() => double.Parse(NextString());
}
partial class LIB_Tree
{
int N;
List<int>[] path;
Dictionary<int, int>[] pathWithCount;
List<(int u, int v)> edges;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_Tree(long n)
{
N = (int)n;
path = Enumerable.Repeat(0, N).Select(_ => new List<int>()).ToArray();
pathWithCount = Enumerable.Repeat(0, N).Select(_ => new Dictionary<int, int>()).ToArray();
edges = new List<(int u, int v)>();
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void AddPath(long u, long v)
{
if (u >= N || v >= N) throw new Exception();
path[u].Add((int)v);
path[v].Add((int)u);
pathWithCount[u].Add((int)v, edges.Count);
pathWithCount[v].Add((int)u, edges.Count);
edges.Add(((int)u, (int)v));
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public int[] GetSurround(long u) => path[u].ToArray();
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public List<(long node, long parent)> BFSFromRoot(long root)
{
var bfsList = new List<(long node, long parent)>();
var q = new Queue<int>();
var done = new bool[N];
bfsList.Add((root, -1));
done[root] = true;
q.Enqueue((int)root);
while (q.Count > 0)
{
var w = q.Dequeue();
foreach (var edge in pathWithCount[w])
{
var i = edge.Key;
if (done[i]) continue;
done[i] = true;
q.Enqueue(i);
bfsList.Add((i, w));
}
}
return bfsList;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public long[] GetDistanceFrom(long root)
{
var ret = new long[N];
foreach (var item in BFSFromRoot(root))
{
if (item.parent == -1) continue;
ret[item.node] = ret[item.parent] + 1;
}
return ret;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public int[] GetJuusin()
{
var center = new List<int>();
var dp = new long[N];
foreach (var item in BFSFromLeaf(0))
{
dp[item.node] += 1;
var ok = false;
foreach (var edge in path[item.node])
{
var idx = edge;
if (idx == item.parent) continue;
dp[item.node] += dp[idx];
if (dp[idx] <= N / 2) ok = true;
}
if (ok)
{
if (N - dp[item.node] <= N / 2)
{
center.Add((int)item.node);
}
}
}
return center.ToArray();
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public int[] GetTyokkei()
{
var dist1 = GetDistanceFrom(0);
var maxPos = 0;
var maxDist = 0L;
for (var i = 0; i < N; i++)
{
if (maxDist < dist1[i])
{
maxDist = dist1[i];
maxPos = i;
}
}
var dist2 = new int[N];
var parent = new int[N];
maxDist = 0;
var anotherMaxPos = 0L;
foreach (var item in BFSFromRoot(maxPos))
{
parent[item.node] = (int)item.parent;
if (item.parent == -1) continue;
dist2[item.node] = dist2[item.parent] + 1;
if (maxDist < dist2[item.node])
{
maxDist = dist2[item.node];
anotherMaxPos = item.node;
}
}
var nownode = (int)anotherMaxPos;
var ret = new List<int>();
while (nownode != -1)
{
ret.Add(nownode);
nownode = parent[nownode];
}
return ret.ToArray();
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public List<(long node, long parent)> BFSFromLeaf(long root) => BFSFromRoot(root).ToArray().Reverse().ToList();
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public (long node, long parent, long direction)[] EulerTour(long root)
{
var eulerList = new (long node, long parent, long direction)[N << 1];
ref var eulerListRef = ref eulerList[0];
var stack = new int[N << 1];
ref var stackref = ref stack[0];
var si = 0;
Unsafe.Add(ref stackref, si++) = (int)root + 1;
var idx = 0;
var par = new int[N];
ref var parref = ref par[0];
Unsafe.Add(ref parref, (int)root) = -1;
while (si > 0)
{
var vtx = Unsafe.Add(ref stackref, --si);
if (vtx < 0)
{
vtx *= -1;
--vtx;
Unsafe.Add(ref eulerListRef, idx) = (vtx, Unsafe.Add(ref parref, vtx), -1);
}
else
{
Unsafe.Add(ref stackref, si++) = -vtx;
--vtx;
var pare = Unsafe.Add(ref parref, vtx);
Unsafe.Add(ref eulerListRef, idx) = (vtx, pare, 1);
foreach (var edge in path[vtx])
{
var item = edge;
if (item == pare) continue;
Unsafe.Add(ref parref, item) = vtx;
Unsafe.Add(ref stackref, si++) = item + 1;
}
}
++idx;
}
return eulerList;
}
}
}