結果
| 問題 | No.768 Tapris and Noel play the game on Treeone |
| ユーザー |
 kzrnm
|
| 提出日時 | 2022-10-28 18:10:10 |
| 言語 | C# (.NET 8.0.203) |
| 結果 |
AC
|
| 実行時間 | 212 ms / 2,000 ms |
| コード長 | 38,809 bytes |
| コンパイル時間 | 16,013 ms |
| コンパイル使用メモリ | 144,904 KB |
| 実行使用メモリ | 60,744 KB |
| 最終ジャッジ日時 | 2023-09-19 09:44:21 |
| 合計ジャッジ時間 | 21,173 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 80 ms
28,688 KB |
| testcase_01 | AC | 80 ms
28,612 KB |
| testcase_02 | AC | 81 ms
28,508 KB |
| testcase_03 | AC | 81 ms
28,784 KB |
| testcase_04 | AC | 81 ms
28,956 KB |
| testcase_05 | AC | 80 ms
28,856 KB |
| testcase_06 | AC | 80 ms
28,680 KB |
| testcase_07 | AC | 152 ms
46,784 KB |
| testcase_08 | AC | 111 ms
37,228 KB |
| testcase_09 | AC | 115 ms
41,036 KB |
| testcase_10 | AC | 108 ms
36,660 KB |
| testcase_11 | AC | 204 ms
56,704 KB |
| testcase_12 | AC | 200 ms
58,956 KB |
| testcase_13 | AC | 195 ms
56,000 KB |
| testcase_14 | AC | 205 ms
55,992 KB |
| testcase_15 | AC | 209 ms
57,760 KB |
| testcase_16 | AC | 210 ms
57,964 KB |
| testcase_17 | AC | 212 ms
58,352 KB |
| testcase_18 | AC | 191 ms
60,744 KB |
| testcase_19 | AC | 186 ms
57,988 KB |
| testcase_20 | AC | 178 ms
57,328 KB |
| testcase_21 | AC | 177 ms
56,124 KB |
| 20evil_special_uni1.txt | AC | 200 ms
60,036 KB |
| 20evil_special_uni2.txt | AC | 195 ms
189,712 KB |
コンパイルメッセージ
Determining projects to restore... Restored /home/judge/data/code/main.csproj (in 138 ms). .NET 向け Microsoft (R) Build Engine バージョン 17.0.0-preview-21470-01+cb055d28f Copyright (C) Microsoft Corporation.All rights reserved. プレビュー版の .NET を使用しています。https://aka.ms/dotnet-core-preview をご覧ください main -> /home/judge/data/code/bin/Release/net6.0/main.dll main -> /home/judge/data/code/bin/Release/net6.0/publish/
ソースコード
using AtCoder.Internal;
using Kzrnm.Competitive;
using Kzrnm.Competitive.IO;
using System;
using System.Buffers;
using System.Buffers.Text;
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.Runtime.InteropServices;
using System.Text;
using 凾 = System.Runtime.CompilerServices.MethodImplAttribute;
partial class Program
{
const bool __ManyTestCases = false;
#if !LOCAL_RUNNING
static void Main()=>new Program(new PropertyConsoleReader(),new Utf8ConsoleWriter()).Run();
[凾(256)]
#endif
private ConsoleOutput? Calc()
{
int N = cr;
var tree = GraphBuilder.CreateTree(N, cr).ToTree();
var dp = tree.Rerooting().Run<bool, Op>().Select((b, i) => (b, i)).Where(t => !t.b).Select(t => t.i + 1).ToArray();
cw.WriteLine(dp.Length);
if (dp.Length > 0) cw.WriteLines(dp);
return null;
}
}
struct Op : IRerootingOperator<bool, GraphEdge>
{
public bool Identity => default;
[凾(256)]
public bool Merge(bool x, bool y) => x || y;
[凾(256)]
public bool Propagate(bool x, int parent, GraphEdge edge) => !x;
}
#region Expanded by https://github.com/kzrnm/SourceExpander
//LICENSE:
//https://github.com/kzrnm/Kzrnm.Competitive/blob/master/LICENSE
//https://github.com/kzrnm/Kzrnm.Competitive/blob/master/3rd-party%20Licenses.txt
#pragma warning disable
namespace AtCoder.Internal{public class CSR<TEdge>:IEnumerable<(int from,TEdge edge)>{public readonly int[]Start;public readonly TEdge[]EList;public CSR(int n,ICollection<(int from,TEdge e)>edges){Start=new int[n+1];EList=new TEdge[edges.Count];foreach(var(from,_)in edges){Start[from+1]++;}for(int i=1;i<=n;i++){Start[i]+=Start[i-1];}var counter=(int[])Start.Clone();foreach(var(from,e)in edges){EList[counter[from]++]=e;}}public Enumerator GetEnumerator()=>new Enumerator(this);IEnumerator<(int from,TEdge edge)>IEnumerable<(int from,TEdge edge)>.GetEnumerator()=>GetEnumerator();IEnumerator IEnumerable.GetEnumerator()=>GetEnumerator();public struct Enumerator:IEnumerator<(int from,TEdge edge)>{public Enumerator(CSR<TEdge>g){_g=g;index=-1;start=0;}private readonly CSR<TEdge>_g;private int index;private int start;public(int from,TEdge edge)Current=>(start,_g.EList[index]);object IEnumerator.Current=>Current;[凾(256)]public bool MoveNext(){if( ++index<_g.Start[start+1])return true;return MoveNextStart();}private bool MoveNextStart(){for( ++start;start+1<_g.Start.Length;++start)if(index<_g.Start[start+1])return true;return false;}public void Reset(){index=-1;start=0;}void IDisposable.Dispose(){}}}}
namespace Kzrnm.Competitive.IO{using static Utf8Parser;using _R=ConsoleReader;public class ConsoleReader{internal const int BufSize=1<<12;internal readonly Stream input;internal readonly Encoding encoding;internal readonly byte[]buf;internal int pos;internal int len;[凾(256)]public ConsoleReader():this(Console.OpenStandardInput(),Console.InputEncoding,BufSize){}[凾(256)]public ConsoleReader(Stream input,Encoding encoding):this(input,encoding,BufSize){}[凾(256)]public ConsoleReader(Stream input,Encoding encoding,int bufferSize){this.input=input;this.encoding=encoding;buf=new byte[bufferSize];}[凾(256)]private void FillEntireNumber(){if((uint)pos>=(uint)buf.Length)FillNextBuffer();while(buf[pos]<=' ')if( ++pos>=len)FillNextBuffer();if(pos+21>=buf.Length&&buf[buf.Length-1]>' ')FillEntireNumberImpl();}private void FillEntireNumberImpl(){buf.AsSpan(pos,len-pos).CopyTo(buf);len-=pos;pos=0;var numberOfBytes=input.Read(buf,len,buf.Length-len);if(numberOfBytes==0)buf[len++]=10;else if(numberOfBytes+len<buf.Length)buf[buf.Length-1]=10;len+=numberOfBytes;}private void FillNextBuffer(){if((len=input.Read(buf,0,buf.Length))==0){buf[0]=10;len=1;}else if(len<buf.Length)buf[buf.Length-1]=10;pos=0;}[凾(256)]internal byte ReadByte(){if(pos>=len)FillNextBuffer();return buf[pos++];}[凾(256)]public T Read<T>(){if(typeof(T)==typeof(int))return(T)(object)Int();if(typeof(T)==typeof(uint))return(T)(object)UInt();if(typeof(T)==typeof(long))return(T)(object)Long();if(typeof(T)==typeof(ulong))return(T)(object)ULong();if(typeof(T)==typeof(double))return(T)(object)Double();if(typeof(T)==typeof(decimal))return(T)(object)Decimal();if(typeof(T)==typeof(char))return(T)(object)Char();if(typeof(T)==typeof(string))return(T)(object)Ascii();return Throw<T>();}static T Throw<T>()=>throw new NotSupportedException(typeof(T).Name);[凾(256)]public int Int(){FillEntireNumber();TryParse(buf.AsSpan(pos),out int v,out int bc);pos+=bc;return v;}[凾(256)]public uint UInt(){FillEntireNumber();TryParse(buf.AsSpan(pos),out uint v,out int bc);pos+=bc;return v;}[凾(256)]public long Long(){FillEntireNumber();TryParse(buf.AsSpan(pos),out long v,out int bc);pos+=bc;return v;}[凾(256)]public ulong ULong(){FillEntireNumber();TryParse(buf.AsSpan(pos),out ulong v,out int bc);pos+=bc;return v;}[凾(256)]public double Double(){FillEntireNumber();TryParse(buf.AsSpan(pos),out double v,out int bc);pos+=bc;return v;}[凾(256)]public decimal Decimal(){FillEntireNumber();TryParse(buf.AsSpan(pos),out decimal v,out int bc);pos+=bc;return v;}[凾(256)]public string String(){var sb=new List<byte>();;byte b;do b=ReadByte();while(b<=' ');do{sb.Add(b);b=ReadByte();}while(' '<b);return encoding.GetString(sb.ToArray());}[凾(256)]public string Ascii(){var sb=new StringBuilder();byte b;do b=ReadByte();while(b<=' ');do{sb.Append((char)b);b=ReadByte();}while(' '<b);return sb.ToString();}[凾(256)]public string Line(){var sb=new List<byte>();byte b;do b=ReadByte();while(b<=' ');do{sb.Add(b);b=ReadByte();}while(b!='\n'&&b!='\r');return encoding.GetString(sb.ToArray());}[凾(256)]public char Char(){byte b;do b=ReadByte();while(b<=' ');return(char)b;}[凾(256)]public int Int0()=>Int()-1;[凾(256)]public uint UInt0()=>UInt()-1;[凾(256)]public long Long0()=>Long()-1;[凾(256)]public ulong ULong0()=>ULong()-1;[凾(256)]public static implicit operator int(_R cr)=>cr.Int();[凾(256)]public static implicit operator uint(_R cr)=>cr.UInt();[凾(256)]public static implicit operator long(_R cr)=>cr.Long();[凾(256)]public static implicit operator ulong(_R cr)=>cr.ULong();[凾(256)]public static implicit operator double(_R cr)=>cr.Double();[凾(256)]public static implicit operator decimal(_R cr)=>cr.Decimal();[凾(256)]public static implicit operator string(_R cr)=>cr.Ascii();public T[]Repeat<T>(int count){var arr=new T[count];for(int i=0;i<arr.Length;i++)arr[i]=Read<T>();return arr;}}}
namespace Kzrnm.Competitive.IO{public sealed class PropertyConsoleReader:ConsoleReader{public PropertyConsoleReader():base(){}public PropertyConsoleReader(Stream input,Encoding encoding):base(input,encoding){}public PropertyConsoleReader(Stream input,Encoding encoding,int bufferSize):base(input,encoding,bufferSize){}public new int Int=>Int();public new int Int0=>Int0();public new uint UInt=>UInt();public new uint UInt0=>UInt0();public new long Long=>Long();public new long Long0=>Long0();public new ulong ULong=>ULong();public new ulong ULong0=>ULong0();public new double Double=>Double();public new decimal Decimal=>Decimal();public new string String=>String();public new string Ascii=>Ascii();public new string Line=>Line();public new char Char=>Char();}}
namespace Kzrnm.Competitive.IO{using static Utf8Formatter;using _W=Utf8ConsoleWriter;public sealed class Utf8ConsoleWriter:IDisposable{internal static readonly UTF8Encoding Utf8NoBom=new UTF8Encoding(false);internal const int BufSize=1<<12;internal readonly Stream output;internal byte[]buf;internal int len;public Utf8ConsoleWriter():this(Console.OpenStandardOutput()){}public Utf8ConsoleWriter(Stream output):this(output,BufSize){}public Utf8ConsoleWriter(Stream output,int bufferSize){this.output=output;buf=new byte[bufferSize];}public StreamWriter ToStreamWriter(){Flush();return new StreamWriter(output,Utf8NoBom);}[凾(256)]public void Flush(){output.Write(buf,0,len);len=0;}void IDisposable.Dispose()=>Flush();[凾(256)]private Span<byte>EnsureBuf(int size){if(buf.Length-len<size){Flush();}return buf.AsSpan(len,size);}[凾(256|512)]public _W Write<T>(T v){void FormatFloat(double d,out int b)=>TryFormat(d,EnsureBuf(Math.Max(25+(int)Math.Log10(Math.Abs(d)),32)),out b,new StandardFormat('F',20));void FormatDec(decimal d,out int b)=>TryFormat(d,EnsureBuf(Math.Max(25+(int)Math.Log10((double)Math.Abs(d)),32)),out b,new StandardFormat('F',20));int bw;if(typeof(T)==typeof(int))TryFormat((int)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(long))TryFormat((long)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(uint))TryFormat((uint)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(ulong))TryFormat((ulong)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(short))TryFormat((short)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(ushort))TryFormat((ushort)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(byte))TryFormat((byte)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(sbyte))TryFormat((sbyte)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(float))FormatFloat((float)(object)v,out bw);else if(typeof(T)==typeof(double))FormatFloat((double)(object)v,out bw);else if(typeof(T)==typeof(decimal))FormatDec((decimal)(object)v,out bw);else if(typeof(T)==typeof(char)){var dst=EnsureBuf(6);var c=(char)(object)v;if(c<0x007f){dst[0]=(byte)c;bw=1;}else{Span<char>s=stackalloc char[1]{c};bw=Utf8NoBom.GetBytes(s,dst);}}else if(v is char[]charr)return Write(charr.AsSpan());else if(v is IUtf8ConsoleWriterFormatter f){f.Write(this);return this;}else return Write(v.ToString().AsSpan());len+=bw;return this;}[凾(256|512)]public _W Write(ReadOnlySpan<char>v){var mlen=Utf8NoBom.GetMaxByteCount(v.Length);if(mlen>buf.Length){Flush();buf=new byte[mlen*2];}else if(mlen>buf.Length-len){Flush();}var bw=Utf8NoBom.GetBytes(v,buf.AsSpan(len));len+=bw;return this;}[凾(256)]public _W WriteLine()=>Write('\n');[凾(256)]public _W WriteLine<T>(T v){Write(v);return Write('\n');}[凾(256)]public _W WriteLine(ReadOnlySpan<char>v){Write(v);return Write('\n');}[凾(256)]public _W WriteLineJoin<T>(IEnumerable<T>col)=>WriteMany(' ',col);[凾(256)]public _W WriteLineJoin<T1,T2>((T1,T2)tuple){Write(tuple.Item1);Write(' ');return WriteLine(tuple.Item2);}[凾(256)]public _W WriteLineJoin<T1,T2,T3>((T1,T2,T3)tuple){Write(tuple.Item1);Write(' ');Write(tuple.Item2);Write(' ');return WriteLine(tuple.Item3);}[凾(256)]public _W WriteLineJoin<T1,T2,T3,T4>((T1,T2,T3,T4)tuple){Write(tuple.Item1);Write(' ');Write(tuple.Item2);Write(' ');Write(tuple.Item3);Write(' ');return WriteLine(tuple.Item4);}[凾(256)]public _W WriteLineJoin<TTuple>(TTuple tuple)where TTuple:ITuple{var col=new object[tuple.Length];for(int i=0;i<col.Length;i++){if(i!=0)Write(' ');Write(tuple[i]);}return WriteLine();}[凾(256)]public _W WriteLineJoin(params object[]col)=>WriteMany(' ',col);[凾(256)]public _W WriteLineJoin<T1,T2>(T1 v1,T2 v2){Write(v1);Write(' ');return WriteLine(v2);}[凾(256)]public _W WriteLineJoin<T1,T2,T3>(T1 v1,T2 v2,T3 v3){Write(v1);Write(' ');Write(v2);Write(' ');return WriteLine(v3);}[凾(256)]public _W WriteLineJoin<T1,T2,T3,T4>(T1 v1,T2 v2,T3 v3,T4 v4){Write(v1);Write(' ');Write(v2);Write(' ');Write(v3);Write(' ');return WriteLine(v4);}[凾(256)]public _W WriteLineJoin<T>(params T[]col)=>WriteMany(' ',(ReadOnlySpan<T>)col);[凾(256)]public _W WriteLineJoin<T>(Span<T>col)=>WriteMany(' ',(ReadOnlySpan<T>)col);[凾(256)]public _W WriteLineJoin<T>(ReadOnlySpan<T>col)=>WriteMany(' ',col);[凾(256)]public _W WriteLines<T>(IEnumerable<T>col)=>WriteMany('\n',col);[凾(256)]public _W WriteLines<T>(T[]col)=>WriteMany('\n',(ReadOnlySpan<T>)col);[凾(256)]public _W WriteLines<T>(Span<T>col)=>WriteMany('\n',(ReadOnlySpan<T>)col);[凾(256)]public _W WriteLines<T>(ReadOnlySpan<T>col)=>WriteMany('\n',col);[凾(256)]public _W WriteGrid<T>(IEnumerable<IEnumerable<T>>cols){foreach(var col in cols)WriteLineJoin(col);return this;}[凾(256)]public _W WriteGrid<TTuple>(IEnumerable<TTuple>tuples)where TTuple:ITuple{foreach(var tup in tuples)WriteLineJoin(tup);return this;}[凾(256)]private _W WriteMany<T>(char sep,IEnumerable<T>col){if(col is T[]array)return WriteMany(sep,(ReadOnlySpan<T>)array);var en=col.GetEnumerator();if(en.MoveNext()){Write(en.Current);while(en.MoveNext()){Write(sep);Write(en.Current);}}return WriteLine();}[凾(256)]private _W WriteMany<T>(char sep,ReadOnlySpan<T>col){if(col.Length>0){Write(col[0]);foreach(var c in col.Slice(1)){Write(sep);Write(c);}}return WriteLine();}}public interface IUtf8ConsoleWriterFormatter{void Write(_W cw);}}
namespace Kzrnm.Competitive{using O=ConsoleOutput;public static class ConsoleOutputExt{[凾(256)]public static O ToConsoleOutput<T>(this T f)where T:IUtf8ConsoleWriterFormatter{var cw=O.cw;f.Write(cw);return cw.WriteLine();}}public struct ConsoleOutput{public static Utf8ConsoleWriter cw;public static implicit operator O(int v)=>cw.WriteLine(v);public static implicit operator O(long v)=>cw.WriteLine(v);public static implicit operator O(uint v)=>cw.WriteLine(v);public static implicit operator O(ulong v)=>cw.WriteLine(v);public static implicit operator O(double v)=>cw.WriteLine(v);public static implicit operator O(decimal v)=>cw.WriteLine(v);public static implicit operator O(char v)=>cw.WriteLine(v);public static implicit operator O(ReadOnlySpan<char>v)=>cw.WriteLine(v);public static implicit operator O(char[]v)=>cw.WriteLine((ReadOnlySpan<char>)v);public static implicit operator O(string v)=>cw.WriteLine((ReadOnlySpan<char>)v);public static implicit operator O(bool v)=>cw.WriteLine((ReadOnlySpan<char>)(v?"Yes":"No"));public static implicit operator O(Utf8ConsoleWriter _)=>default;}}
internal partial class Program{public PropertyConsoleReader cr;public Utf8ConsoleWriter cw;public Program(PropertyConsoleReader r,Utf8ConsoleWriter w){cr=r;ConsoleOutput.cw=cw=w;CultureInfo.CurrentCulture=CultureInfo.InvariantCulture;}public void Run(){int Q=__ManyTestCases?cr.Int:1;while( --Q>=0)Calc();cw.Flush();}}
namespace Kzrnm.Competitive{public class SparseTable<TValue,TOp>where TOp:struct,ISparseTableOperator<TValue>{private static TOp op=default;private readonly TValue[][]st;public int Length{get;}public SparseTable(TValue[]array){Length=array.Length;st=new TValue[BitOperations.Log2((uint)Length)+1][];st[0]=(TValue[])array.Clone();for(int i=1;i<st.Length;i++){var stp=st[i-1];var sti=st[i]=new TValue[Length-(1<<i)+1];for(int j=0;j<sti.Length;j++)sti[j]=op.Operate(stp[j],stp[j+(1<<(i-1))]);}}[凾(256)]public TValue Slice(int l,int length)=>Prod(l,l+length);[凾(256)]public TValue Prod(int l,int r){var b=BitOperations.Log2((uint)(r-l));var stb=st[b];return op.Operate(stb[l],stb[r-(1<<b)]);}private struct DebugItem{public DebugItem(int l,int r,TValue value){if(r-l==1)key=$"[{l}]";else key=$"[{l}-{r})";this.value=value;}private readonly string key;private readonly TValue value;}private class DebugView{private readonly SparseTable<TValue,TOp>st;public DebugView(SparseTable<TValue,TOp>st){this.st=st;}public DebugItem[]Items{get{var items=new List<DebugItem>(st.st.Length*st.Length);for(int b=0;b<st.st.Length;b++){var len=1<<b;var stb=st.st[b];for(int i=0;i<stb.Length;i++)items.Add(new DebugItem(i,i+len,stb[i]));}return items.ToArray();}}}}}
namespace Kzrnm.Competitive{public interface ISparseTableOperator<T>{T Operate(T x,T y);}}
namespace Kzrnm.Competitive{public static class __ArrayExtension{[凾(256)]public static T[]Fill<T>(this T[]arr,T value){arr.AsSpan().Fill(value);return arr;}[凾(256)]public static T[]Sort<T>(this T[]arr){Array.Sort(arr);return arr;}[凾(256)]public static string[]Sort(this string[]arr)=>Sort(arr,StringComparer.Ordinal);[凾(256)]public static T[]Sort<T,U>(this T[]arr,Func<T,U>selector)where U:IComparable<U>{Array.Sort(arr.Select(selector).ToArray(),arr);return arr;}[凾(256)]public static T[]Sort<T>(this T[]arr,Comparison<T>comparison){Array.Sort(arr,comparison);return arr;}[凾(256)]public static T[]Sort<T>(this T[]arr,IComparer<T>comparer){Array.Sort(arr,comparer);return arr;}[凾(256)]public static T[]Reverse<T>(this T[]arr){Array.Reverse(arr);return arr;}[凾(256)]public static ref T Get<T>(this T[]arr,int index){if(index<0)index+=arr.Length;return ref arr[index];}[凾(256)]public static ref readonly T GetOrDummy<T>(this ReadOnlySpan<T>arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[凾(256)]public static ref T GetOrDummy<T>(this Span<T>arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[凾(256)]public static ref T GetOrDummy<T>(this T[]arr,int index,T dummy=default)=>ref GetOrDummy(arr.AsSpan(),index,dummy);[凾(256)]public static ref T GetOrDummy<T>(this T[][]arr,int index1,int index2,T dummy=default){if((uint)index1<(uint)arr.Length)return ref GetOrDummy(arr[index1],index2,dummy);Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[凾(256)]public static ref T GetOrDummy<T>(this T[][][]arr,int index1,int index2,int index3,T dummy=default){if((uint)index1<(uint)arr.Length)return ref GetOrDummy(arr[index1],index2,index3,dummy);Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}private static class Dummy<T>{public static T dummy;}[凾(256)]public static int FindByBinarySearch<T,TCv>(this T[]arr,TCv value)where TCv:IComparable<T> =>FindByBinarySearch((ReadOnlySpan<T>)arr,value);[凾(256)]public static int FindByBinarySearch<T,TCv>(this Span<T>arr,TCv value)where TCv:IComparable<T> =>FindByBinarySearch((ReadOnlySpan<T>)arr,value);[凾(256)]public static int FindByBinarySearch<T,TCv>(this ReadOnlySpan<T>arr,TCv value)where TCv:IComparable<T>{int ix=arr.BinarySearch(value);if(ix<0)ix=~ix;return ix;}}}
namespace Kzrnm.Competitive{public static class __MemoryMarshalExtension{private class ArrayVal<T>{public T[]arr;}[凾(256)]public static Span<T>AsSpan<T>(this List<T>list,int start=0)=>Unsafe.As<ArrayVal<T>>(list).arr.AsSpan(start,list.Count-start);[凾(256)]public static Span<TTo>Cast<TFrom,TTo>(this Span<TFrom>span)where TFrom:struct where TTo:struct=>MemoryMarshal.Cast<TFrom,TTo>(span);[凾(256)]public static ReadOnlySpan<TTo>Cast<TFrom,TTo>(this ReadOnlySpan<TFrom>span)where TFrom:struct where TTo:struct=>MemoryMarshal.Cast<TFrom,TTo>(span);[凾(256)]public static ref T GetReference<T>(this Span<T>span)=>ref MemoryMarshal.GetReference(span);[凾(256)]public static ref T GetReference<T>(this ReadOnlySpan<T>span)=>ref MemoryMarshal.GetReference(span);}}
namespace Kzrnm.Competitive{public static class __CollectionTupleExtension_Stack{[凾(256)]public static bool TryPop<T1,T2>(this Stack<(T1,T2)>stack,out T1 item1,out T2 item2){var ok=stack.TryPop(out var tuple);(item1,item2)=tuple;return ok;}[凾(256)]public static bool TryPop<T1,T2,T3>(this Stack<(T1,T2,T3)>stack,out T1 item1,out T2 item2,out T3 item3){var ok=stack.TryPop(out var tuple);(item1,item2,item3)=tuple;return ok;}[凾(256)]public static bool TryPeek<T1,T2>(this Stack<(T1,T2)>stack,out T1 item1,out T2 item2){var ok=stack.TryPeek(out var tuple);(item1,item2)=tuple;return ok;}[凾(256)]public static bool TryPeek<T1,T2,T3>(this Stack<(T1,T2,T3)>stack,out T1 item1,out T2 item2,out T3 item3){var ok=stack.TryPeek(out var tuple);(item1,item2,item3)=tuple;return ok;}}}
namespace Kzrnm.Competitive{public class GraphBuilder{internal readonly EdgeContainer<GraphEdge>edgeContainer;public GraphBuilder(int size,bool isDirected){edgeContainer=new EdgeContainer<GraphEdge>(size,isDirected);}public static GraphBuilder Create(int count,ConsoleReader cr,int edgeCount,bool isDirected){var gb=new GraphBuilder(count,isDirected);for(var i=0;i<edgeCount;i++)gb.Add(cr.Int0(),cr.Int0());return gb;}public static GraphBuilder<int>CreateWithEdgeIndex(int count,ConsoleReader cr,int edgeCount,bool isDirected){var gb=new GraphBuilder<int>(count,isDirected);for(var i=0;i<edgeCount;i++)gb.Add(cr.Int0(),cr.Int0(),i);return gb;}public static GraphBuilder CreateTree(int count,ConsoleReader cr){var gb=new GraphBuilder(count,false);for(var i=1;i<count;i++)gb.Add(cr.Int0(),cr.Int0());return gb;}[凾(256)]public void Add(int from,int to)=>edgeContainer.Add(from,new GraphEdge(to));public SimpleGraph<GraphNode,GraphEdge>ToGraph()=>GraphBuilderLogic.ToGraph<SimpleGraph<GraphNode,GraphEdge>,GraphNode,GraphEdge,TOp>(edgeContainer);public TreeGraph<TreeNode,GraphEdge>ToTree(int root=0)=>GraphBuilderLogic.ToTree<TreeGraph<TreeNode,GraphEdge>,TreeNode,GraphEdge,TOp>(edgeContainer,root);struct TOp:IGraphBuildOperator<SimpleGraph<GraphNode,GraphEdge>,GraphNode,GraphEdge>,ITreeBuildOperator<TreeGraph<TreeNode,GraphEdge>,TreeNode,GraphEdge>{[凾(256)]public SimpleGraph<GraphNode,GraphEdge>Graph(GraphNode[]nodes,CSR<GraphEdge>edges)=>new SimpleGraph<GraphNode,GraphEdge>(nodes,edges);[凾(256)]public GraphNode Node(int i,GraphEdge[]parents,GraphEdge[]children)=>new GraphNode(i,parents,children);[凾(256)]public TreeGraph<TreeNode,GraphEdge>Tree(TreeNode[]nodes,int root,HeavyLightDecomposition<TreeNode,GraphEdge>hl)=>new TreeGraph<TreeNode,GraphEdge>(nodes,root,hl);[凾(256)]public TreeNode TreeNode(int i,int size,TreeNode parent,GraphEdge edge,GraphEdge[]children)=>new TreeNode(i,size,edge.Reversed(parent.Index),parent.Depth+1,children);[凾(256)]public TreeNode TreeRootNode(int i,int size,GraphEdge[]children)=>new TreeNode(i,size,GraphEdge.None,0,children);}}public readonly struct GraphEdge:IGraphEdge,IReversable<GraphEdge>,IEquatable<GraphEdge>{public static GraphEdge None{get;}=new GraphEdge(-1);public GraphEdge(int to){To=to;}public int To{get;}[凾(256)]public static implicit operator int(GraphEdge e)=>e.To;public override string ToString()=>To.ToString();[凾(256)]public GraphEdge Reversed(int from)=>new GraphEdge(from);public override int GetHashCode()=>To;public override bool Equals(object obj)=>obj is GraphEdge edge&&Equals(edge);public bool Equals(GraphEdge other)=>To==other.To;public static bool operator==(GraphEdge left,GraphEdge right)=>left.Equals(right);public static bool operator!=(GraphEdge left,GraphEdge right)=>!left.Equals(right);}public class GraphNode:IGraphNode<GraphEdge>,IEquatable<GraphNode>{public GraphNode(int i,GraphEdge[]parents,GraphEdge[]children){Index=i;Parents=parents;Children=children;}public int Index{get;}public GraphEdge[]Parents{get;}public GraphEdge[]Children{get;}public bool IsDirected=>Parents!=Children;public override string ToString()=>$"children: {string.Join(",",Children)}";public override bool Equals(object obj)=>obj is GraphNode d&&Equals(d);public bool Equals(GraphNode other)=>Index==other?.Index;public override int GetHashCode()=>Index;}public class TreeNode:ITreeNode<GraphEdge>,IEquatable<TreeNode>{public TreeNode(int i,int size,GraphEdge parent,int depth,GraphEdge[]children){Index=i;Parent=parent;Children=children;Depth=depth;Size=size;}public int Index{get;}public GraphEdge Parent{get;}public GraphEdge[]Children{get;}public int Depth{get;}public int Size{get;}public override string ToString()=>$"children: {string.Join(",",Children)}";public override bool Equals(object obj)=>obj is TreeNode node&&Equals(node);public bool Equals(TreeNode other)=>other!=null&&Index==other.Index;public override int GetHashCode()=>Index;}}
namespace Kzrnm.Competitive{public class GraphBuilder<T>{internal readonly EdgeContainer<GraphEdge<T>>edgeContainer;public GraphBuilder(int size,bool isDirected){edgeContainer=new EdgeContainer<GraphEdge<T>>(size,isDirected);}[凾(256)]public void Add(int from,int to,T data)=>edgeContainer.Add(from,new GraphEdge<T>(to,data));public SimpleGraph<GraphNode<GraphEdge<T>>,GraphEdge<T>>ToGraph()=>GraphBuilderLogic.ToGraph<SimpleGraph<GraphNode<GraphEdge<T>>,GraphEdge<T>>,GraphNode<GraphEdge<T>>,GraphEdge<T>,TOp>(edgeContainer);public TreeGraph<TreeNode<T>,GraphEdge<T>>ToTree(int root=0)=>GraphBuilderLogic.ToTree<TreeGraph<TreeNode<T>,GraphEdge<T>>,TreeNode<T>,GraphEdge<T>,TOp>(edgeContainer,root);struct TOp:IGraphBuildOperator<SimpleGraph<GraphNode<GraphEdge<T>>,GraphEdge<T>>,GraphNode<GraphEdge<T>>,GraphEdge<T>>,ITreeBuildOperator<TreeGraph<TreeNode<T>,GraphEdge<T>>,TreeNode<T>,GraphEdge<T>>{[凾(256)]public SimpleGraph<GraphNode<GraphEdge<T>>,GraphEdge<T>>Graph(GraphNode<GraphEdge<T>>[]nodes,CSR<GraphEdge<T>>edges)=>new SimpleGraph<GraphNode<GraphEdge<T>>,GraphEdge<T>>(nodes,edges);[凾(256)]public GraphNode<GraphEdge<T>>Node(int i,GraphEdge<T>[]parents,GraphEdge<T>[]children)=>new GraphNode<GraphEdge<T>>(i,parents,children);[凾(256)]public TreeGraph<TreeNode<T>,GraphEdge<T>>Tree(TreeNode<T>[]nodes,int root,HeavyLightDecomposition<TreeNode<T>,GraphEdge<T>>hl)=>new TreeGraph<TreeNode<T>,GraphEdge<T>>(nodes,root,hl);[凾(256)]public TreeNode<T>TreeNode(int i,int size,TreeNode<T>parent,GraphEdge<T>edge,GraphEdge<T>[]children)=>new TreeNode<T>(i,size,edge.Reversed(parent.Index),parent.Depth+1,children);[凾(256)]public TreeNode<T>TreeRootNode(int i,int size,GraphEdge<T>[]children)=>new TreeNode<T>(i,size,GraphEdge<T>.None,0,children);}}public readonly struct GraphEdge<T>:IGraphEdge,IGraphData<T>,IReversable<GraphEdge<T>>,IEquatable<GraphEdge<T>>{public static GraphEdge<T>None{get;}=new GraphEdge<T>(-1,default);public GraphEdge(int to,T data){To=to;Data=data;}public T Data{get;}public int To{get;}[凾(256)]public static implicit operator int(GraphEdge<T>e)=>e.To;public override string ToString()=>$"to:{To}, Data:{Data}";[凾(256)]public void Deconstruct(out int to,out T data){to=To;data=Data;}[凾(256)]public GraphEdge<T>Reversed(int from)=>new GraphEdge<T>(from,Data);public override int GetHashCode()=>To;public override bool Equals(object obj)=>obj is GraphEdge<T>edge&&Equals(edge);public bool Equals(GraphEdge<T>other)=>To==other.To;public static bool operator==(GraphEdge<T>left,GraphEdge<T>right)=>left.Equals(right);public static bool operator!=(GraphEdge<T>left,GraphEdge<T>right)=>!left.Equals(right);}public class GraphNode<TEdge>:IGraphNode<TEdge>,IEquatable<GraphNode<TEdge>>where TEdge:IGraphEdge{public GraphNode(int i,TEdge[]parents,TEdge[]children){Index=i;Parents=parents;Children=children;}public int Index{get;}public TEdge[]Parents{get;}public TEdge[]Children{get;}public bool IsDirected=>Parents!=Children;public override string ToString()=>$"children: {string.Join(",",Children)}";public override bool Equals(object obj)=>obj is GraphNode<TEdge>d&&Equals(d);public bool Equals(GraphNode<TEdge>other)=>Index==other?.Index;public override int GetHashCode()=>Index;}public class TreeNode<T>:ITreeNode<GraphEdge<T>>,IEquatable<TreeNode<T>>{public TreeNode(int i,int size,GraphEdge<T>parent,int depth,GraphEdge<T>[]children){Index=i;Parent=parent;Children=children;Depth=depth;Size=size;}public int Index{get;}public GraphEdge<T>Parent{get;}public GraphEdge<T>[]Children{get;}public int Depth{get;}public int Size{get;}public override string ToString()=>$"children: {string.Join(",",Children)}";public override bool Equals(object obj)=>obj is TreeNode<T>node&&Equals(node);public bool Equals(TreeNode<T>other)=>other!=null&&Index==other.Index;public override int GetHashCode()=>Index;}}
namespace Kzrnm.Competitive{public class SimpleGraph<TNode,TEdge>:IGraph<TNode,TEdge>where TNode:IGraphNode<TEdge>where TEdge:IGraphEdge{public CSR<TEdge>Edges{get;}internal TNode[]Nodes{get;}[凾(256)]public TNode[]AsArray()=>Nodes;public TNode this[int index]{[凾(256)]get=>Nodes[index];}public int Length=>Nodes.Length;public SimpleGraph(TNode[]array,CSR<TEdge>edges){Nodes=array;Edges=edges;}}public class TreeGraph<TNode,TEdge>:ITreeGraph<TNode,TEdge>where TNode:ITreeNode<TEdge>where TEdge:IGraphEdge{internal TNode[]Nodes{get;}[凾(256)]public TNode[]AsArray()=>Nodes;public TNode this[int index]{[凾(256)]get=>Nodes[index];}public int Length=>Nodes.Length;public int Root{get;}public HeavyLightDecomposition<TNode,TEdge>HlDecomposition{get;}public TreeGraph(TNode[]array,int root,HeavyLightDecomposition<TNode,TEdge>hl){Root=root;Nodes=array;HlDecomposition=hl;}}}
namespace Kzrnm.Competitive{public interface IReversable<T>where T:IGraphEdge{T Reversed(int from);}public interface IGraphEdge{int To{get;}}public interface IWGraphEdge<T>:IGraphEdge{T Value{get;}}public interface IGraphData<T>:IGraphEdge{T Data{get;}}public interface IGraphNode<out TEdge>where TEdge:IGraphEdge{int Index{get;}TEdge[]Parents{get;}TEdge[]Children{get;}bool IsDirected{get;}}public interface ITreeNode<TEdge>where TEdge:IGraphEdge{int Index{get;}TEdge Parent{get;}TEdge[]Children{get;}int Depth{get;}int Size{get;}}public interface IGraphBuildOperator<TGraph,TNode,TEdge>{TNode Node(int i,TEdge[]parents,TEdge[]children);TGraph Graph(TNode[]nodes,CSR<TEdge>edges);}public interface ITreeBuildOperator<TTree,TNode,TEdge>where TNode:ITreeNode<TEdge>where TEdge:IGraphEdge{TNode TreeNode(int i,int size,TNode parent,TEdge parentEdge,TEdge[]children);TNode TreeRootNode(int i,int size,TEdge[]children);TTree Tree(TNode[]nodes,int root,HeavyLightDecomposition<TNode,TEdge>hl);}public interface IGraph<TNode,TEdge>where TNode:IGraphNode<TEdge>where TEdge:IGraphEdge{CSR<TEdge>Edges{get;}TNode[]AsArray();TNode this[int index]{get;}int Length{get;}}public interface ITreeGraph<TNode,TEdge>where TNode:ITreeNode<TEdge>where TEdge:IGraphEdge{int Root{get;}TNode[]AsArray();TNode this[int index]{get;}int Length{get;}HeavyLightDecomposition<TNode,TEdge>HlDecomposition{get;}}public class EdgeContainer<TEdge>where TEdge:IGraphEdge{public int Length{get;}public bool IsDirected{get;}public readonly List<(int from,TEdge edge)>edges;public readonly int[]sizes;public readonly int[]parentSizes;public EdgeContainer(int size,bool isDirected){Length=size;IsDirected=isDirected;sizes=new int[size];parentSizes=isDirected?new int[size]:sizes;edges=new List<(int from,TEdge edge)>(size);}[凾(256)]public void Add(int from,TEdge edge){ ++sizes[from];++parentSizes[edge.To];edges.Add((from,edge));}[凾(256)]public CSR<TEdge>ToCSR()=>new CSR<TEdge>(Length,edges);}internal static class GraphBuilderLogic{[凾(512)]public static TGraph ToGraph<TGraph,TNode,TEdge,TOp>(EdgeContainer<TEdge>edgeContainer)where TGraph:IGraph<TNode,TEdge>where TNode:IGraphNode<TEdge>where TEdge:IGraphEdge,IReversable<TEdge>where TOp:struct,IGraphBuildOperator<TGraph,TNode,TEdge>{var op=new TOp();var res=new TNode[edgeContainer.Length];var csr=edgeContainer.ToCSR();var counter=new int[res.Length];var parentCounter=edgeContainer.IsDirected?new int[res.Length]:counter;var children=SizeToArray<TEdge>(edgeContainer.sizes);var parents=edgeContainer.IsDirected?SizeToArray<TEdge>(edgeContainer.parentSizes):children;for(int i=0;i<res.Length;i++){res[i]=op.Node(i,parents[i],children[i]);foreach(var e in csr.EList.AsSpan(csr.Start[i],csr.Start[i+1]-csr.Start[i])){var to=e.To;children[i][counter[i]++]=e;parents[to][parentCounter[to]++]=e.Reversed(i);}}return op.Graph(res,csr);}[凾(512)]public static TGraph ToTree<TGraph,TNode,TEdge,TOp>(EdgeContainer<TEdge>edgeContainer,int root)where TGraph:ITreeGraph<TNode,TEdge>where TNode:class,ITreeNode<TEdge>where TEdge:IGraphEdge,IReversable<TEdge>where TOp:struct,ITreeBuildOperator<TGraph,TNode,TEdge>{var op=new TOp();int size=edgeContainer.Length;var edges=SizeToArray<TEdge>(edgeContainer.sizes);var idxs=new int[edges.Length];foreach(var(from,e)in edgeContainer.edges.AsSpan()){var to=e.To;edges[from][idxs[from]++]=e;edges[to][idxs[to]++]=e.Reversed(from);}idxs.AsSpan().Clear();var sz=new int[size].Fill(1);var children=SizeToArray<TEdge>(edgeContainer.sizes,-1,root);var parent=new int[size];parent[root]=-1;var stack=new Stack<(int Cur,int Chix)>(size);stack.Push((root,0));while(stack.TryPop(out var cur,out var ci)){var es=edges[cur];if( --ci>=0){var tp=es[ci].To;sz[cur]+=sz[tp];if(sz[tp]>sz[es[0].To])(children[cur][0],children[cur][ci])=(children[cur][ci],children[cur][0]);}if( ++ci<children[cur].Length){var to=es[ci].To;if(parent[cur]==to){var b=es.Length-1;(es[ci],es[b])=(es[b],es[ci]);to=es[ci].To;}stack.Push((cur,ci+1));stack.Push((to,0));children[cur][ci]=es[ci];parent[to]=cur;}}var etid=0;var down=new int[size];var up=new int[size];var nxt=new int[size];var nodes=new TNode[size];stack.Push((root,0));while(stack.TryPop(out var cur,out var ci)){var ch=children[cur];if(ci==0){down[cur]=etid++;nodes[cur]=root==cur?op.TreeRootNode(cur,sz[cur],children[cur]):op.TreeNode(cur,sz[cur],nodes[parent[cur]],edges[cur][^1],children[cur]);}if(ci<ch.Length){var to=ch[ci].To;nxt[to]=ci==0?nxt[cur]:to;stack.Push((cur,ci+1));stack.Push((to,0));}else up[cur]=etid;}var hl=new HeavyLightDecomposition<TNode,TEdge>(nodes,nxt,down,up);return op.Tree(nodes,root,hl);}static T[][]SizeToArray<T>(int[]sizeArray,int offset=0,int root=-1){var a=new T[sizeArray.Length][];for(int i=0;i<sizeArray.Length;i++)a[i]=new T[sizeArray[i]+(root==i?0:offset)];return a;}}public static class GraphExtensions{[凾(256)]public static int LowestCommonAncestor<TNode,TEdge>(this ITreeGraph<TNode,TEdge>tree,int u,int v)where TNode:ITreeNode<TEdge>where TEdge:IGraphEdge=>tree.HlDecomposition.LowestCommonAncestor(u,v);}}
namespace Kzrnm.Competitive{public class HeavyLightDecomposition<TNode,TEdge>where TNode:ITreeNode<TEdge>where TEdge:IGraphEdge{public TNode[]tree;public int[]down;public int[]up;public int[]nxt;public HeavyLightDecomposition(TNode[]tree,int[]nxt,int[]down,int[]up){this.tree=tree;this.nxt=nxt;this.down=down;this.up=up;}[凾(256)]public(int From,int To)Index(int u)=>(down[u],up[u]);[凾(256)]public int LowestCommonAncestor(int u,int v){if(u==v)return u;var f=down[u]+1;var t=down[v]+1;if(t<f)(f,t)=(t,f);return lcaTable[f..t].Node;}[凾(256)]public void PathQuery(int u,int v,bool vertex,Action<int,int>f)=>PathQuery(u,v,vertex,new FWrapper(f));[凾(256)]public void PathQuery<TOp>(int u,int v,bool vertex,TOp f)where TOp:IHlDecompositionOperator{foreach(var(from,to)in new PathEnumerator(this,u,v,vertex))f.Operate(from,to);}[凾(256)]public void PathQuery<TOp>(int u,int v,bool vertex,ref TOp f)where TOp:IHlDecompositionOperator{foreach(var(from,to)in new PathEnumerator(this,u,v,vertex))f.Operate(from,to);}[凾(256)]public void SubtreeQuery(int u,bool vertex,Action<int,int>f)=>SubtreeQuery(u,vertex,new FWrapper(f));[凾(256)]public void SubtreeQuery<TOp>(int u,bool vertex,TOp f)where TOp:IHlDecompositionOperator=>f.Operate(down[u]+(vertex?0:1),up[u]);[凾(256)]public void SubtreeQuery<TOp>(int u,bool vertex,ref TOp f)where TOp:IHlDecompositionOperator=>f.Operate(down[u]+(vertex?0:1),up[u]);private SparseTable<(int Depth,int Node),NodeMinOp>_lcaTable;private SparseTable<(int Depth,int Node),NodeMinOp>lcaTable=>_lcaTable??=BuildLcaTable();private SparseTable<(int Depth,int Node),NodeMinOp>BuildLcaTable(){var arr=new(int Depth,int Node)[down.Length];for(int i=0;i<arr.Length;i++){var n=tree[i];arr[down[i]]=(n.Depth,n.Parent.To);}return new SparseTable<(int Depth,int Node),NodeMinOp>(arr);}private struct NodeMinOp:ISparseTableOperator<(int Depth,int Node)>{[凾(256)]public(int Depth,int Node)Operate((int Depth,int Node)x,(int Depth,int Node)y)=>x.Depth<=y.Depth?x:y;}private readonly struct FWrapper:IHlDecompositionOperator{private readonly Action<int,int>f;public FWrapper(Action<int,int>func){f=func;}[凾(256)]public void Operate(int u,int v)=>f(u,v);}private struct PathEnumerator{HeavyLightDecomposition<TNode,TEdge>hl;(int f,int t)_c;int u,v,lca;Stack<(int f,int t)>desc;St st;public PathEnumerator(HeavyLightDecomposition<TNode,TEdge>hl,int u,int v,bool vertex){lca=hl.LowestCommonAncestor(u,v);desc=BuildDesc(hl,lca,v);_c=default;this.hl=hl;this.u=u;this.v=lca;st=(St)(vertex?0b11:0b01);}public PathEnumerator GetEnumerator()=>this;static Stack<(int f,int t)>BuildDesc(HeavyLightDecomposition<TNode,TEdge>hl,int u,int v){var s=new Stack<(int f,int t)>();var tree=hl.tree;var nxt=hl.nxt;var down=hl.down;while(u!=v){if(nxt[u]==nxt[v]){s.Push((down[u]+1,down[v]+1));break;}else{s.Push((down[nxt[v]],down[v]+1));v=tree[nxt[v]].Parent.To;}}return s;}public(int f,int t)Current=>_c;public bool MoveNext(){var down=hl.down;var nxt=hl.nxt;if(u==v)goto Desc;if(st.HasFlag(St.Start))st&=~St.Start;else u=hl.tree[nxt[u]].Parent.To;if(nxt[u]!=nxt[v]){_c=(down[u]+1,down[nxt[u]]);return true;}if(u!=v){_c=(down[u]+1,down[v]+1);u=v;return true;}Desc:if(st.HasFlag(St.Vertex)){st&=~St.Vertex;var r=hl.down[lca];_c=(r,r+1);return true;}return desc.TryPop(out _c);}[Flags]enum St:byte{Start=1,Vertex=0b10,}}}public interface IHlDecompositionOperator{void Operate(int f,int t);}}
namespace Kzrnm.Competitive{public static class 全方位木DP{[凾(256)]public static Impl<TNode,TEdge>Rerooting<TNode,TEdge>(this ITreeGraph<TNode,TEdge>tree)where TNode:ITreeNode<TEdge>where TEdge:IGraphEdge=>new Impl<TNode,TEdge>(tree);public readonly struct Impl<TNode,TEdge>where TNode:ITreeNode<TEdge>where TEdge:IGraphEdge{public Impl(ITreeGraph<TNode,TEdge>tree){Tree=tree;}private readonly ITreeGraph<TNode,TEdge>Tree;public T[]Run<T,TOp>(TOp op=default)where TOp:struct,IRerootingOperator<T,TEdge>{var tree=Tree.AsArray();var memo=new T[tree.Length];var dp=new T[tree.Length];{var idx=Tree.DfsDescendant();for(int i=idx.Length-1;i>=0;i--){var ix=idx[i];memo[ix]=op.Identity;foreach(var e in tree[ix].Children)memo[ix]=op.Merge(memo[ix],op.Propagate(memo[e.To],ix,e));}}{var stack=new Stack<(int Current,T Prev)>();stack.Push((Tree.Root,op.Identity));while(stack.TryPop(out var tuple)){var(cur,pval)=tuple;var edges=tree[cur].Children;var buf=new T[edges.Length];for(int i=0;i<edges.Length;i++){var e=edges[i];buf[i]=op.Propagate(memo[e.To],cur,e);}var head=new T[buf.Length+1];var tail=new T[buf.Length+1];head[0]=tail[^1]=op.Identity;for(int i=0;i<buf.Length;i++)head[i+1]=op.Merge(head[i],buf[i]);for(int i=buf.Length-1;i>=0;i--)tail[i]=op.Merge(tail[i+1],buf[i]);dp[cur]=op.Merge(pval,head[^1]);for(int i=0;i<edges.Length;i++){var e=edges[i];var dst=e.To;stack.Push((dst,op.Propagate(op.Merge(pval,op.Merge(head[i],tail[i+1])),dst,tree[dst].Parent)));}}}return dp;}}}public interface IRerootingOperator<T,TEdge>where TEdge:IGraphEdge{T Identity{get;}T Merge(T x,T y);T Propagate(T x,int parent,TEdge edge);}}
namespace Kzrnm.Competitive{public static class 木の探索{[凾(256)]public static int[]BfsDescendant<TNode,TEdge>(this ITreeGraph<TNode,TEdge>tree)where TNode:ITreeNode<TEdge>where TEdge:IGraphEdge{var arr=tree.AsArray();var res=new int[arr.Length];res[0]=tree.Root;int tar=1;int cur=0;while((uint)tar<(uint)res.Length){foreach(var e in arr[res[cur++]].Children)res[tar++]=e.To;}return res;}[凾(256)]public static int[]DfsDescendant<TNode,TEdge>(this ITreeGraph<TNode,TEdge>tree)where TNode:ITreeNode<TEdge>where TEdge:IGraphEdge{var down=tree.HlDecomposition.down;var res=new int[down.Length];for(int i=0;i<res.Length;i++)res[down[i]]=i;return res;}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander