結果

問題 No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑
ユーザー tobisatis
提出日時 2025-07-18 22:26:49
言語 C#
(.NET 8.0.404)
結果
WA  
実行時間 -
コード長 6,036 bytes
コンパイル時間 8,129 ms
コンパイル使用メモリ 171,132 KB
実行使用メモリ 260,816 KB
最終ジャッジ日時 2025-07-18 22:27:11
合計ジャッジ時間 17,122 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 WA * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (101 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

#nullable enable

#region
var _input = Array.Empty<string>();
var _iter = 0;
string String()
{
    while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Split(' '), 0);
    return _input[_iter++];
}
T I<T>() where T : IParsable<T> => T.Parse(String(), null);
#endregion

T[] Range<T>(int n, Func<T> F) => Enumerable.Range(0, n).Select(_ => F()).ToArray();

var n = I<int>();
var edges = Range(n - 1, () => (I<int>() - 1, I<int>() - 1));
var sg = new StaticGraph(edges, n, false);
var tree = Tree.TryConstruct(sg)!;
var op = new Op(sg);
var tns = tree.Rerooting<(int, int), Op>(op);
var ans = tns.Select(e => e.Item2).Max() + 1;
Console.WriteLine(ans);

readonly struct Op : Tree.IRerootingOperator<(int, int)>
{
    const int Max = int.MaxValue >> 1;
    public Op(StaticGraph sg) { SG = sg; }
    public readonly StaticGraph SG;
    public (int, int) Identity => (Max, 0);
    public (int, int) ApplyE((int, int) e, int ei)
    {
        return e;
    }
    public (int, int) ApplyV((int, int) e, int v)
    {
        var (ea, _) = e;
        if (ea >= Max) ea = 0;
        var l = SG.Adjacencies(v).Length;
        var ev = ea * l;
        ea++;
        return (ea, ev);
    }
    public (int, int) Merge((int, int) l, (int, int) r)
    {
        var (la, _) = l;
        var (ra, _) = r;
        return (Math.Min(la, ra), 0);
    }
}

class StaticGraph
{
    public int N { get; }
    public bool Directed { get; }
    public ReadOnlySpan<(int next, int edgeIndex)> Adjacencies(int of) => _adjacencyList.Span[of].Span;
    public ReadOnlySpan<(int Ab, int Ad)> Edges => _edges.Span;

    readonly ReadOnlyMemory<ReadOnlyMemory<(int, int)>> _adjacencyList;
    readonly ReadOnlyMemory<(int Ab, int Ad)> _edges;

    public StaticGraph(IReadOnlyList<(int, int)> edges, int verticals, bool directed)
    {
        (N, Directed) = (verticals, directed);
        var al = new List<(int, int)>[verticals];
        for (var i = 0; i < verticals; i++) al[i] = new();
        _edges = edges.ToArray();
        for (var i = 0; i < edges.Count; i++)
        {
            var (ab, ad) = edges[i];
            al[ab].Add((ad, i));
            if (!Directed) al[ad].Add((ab, i));
        }
        var ala = new ReadOnlyMemory<(int, int)>[verticals];
        var dataMemory = new (int, int)[directed ? edges.Count : edges.Count * 2].AsMemory();
        var dataSpan = dataMemory.Span;
        var k = 0;
        for (var i = 0; i < verticals; i++)
        {
            var length = al[i].Count;
            for (var j = 0; j < length; j++) dataSpan[k + j] = al[i][j];
            ala[i] = dataMemory.Slice(k, length);
            k += length;
        }
        _adjacencyList = ala;
    }
}

class Graph { public required StaticGraph StaticGraph { get; init; } }

partial class Tree : Graph
{
    public static Tree? TryConstruct(StaticGraph graph)
    {
        if (graph.Directed || graph.Edges.Length + 1 != graph.N) return null;
        var visited = new bool[graph.N];
        int S(int v, int prev)
        {
            visited[v] = true;
            var res = 1;
            var adjacencies = graph.Adjacencies(v);
            foreach (var (next, _) in adjacencies)
            {
                if (next == prev || visited[next]) continue;
                res += S(next, v);
            }
            return res;
        }
        if (S(0, -1) < graph.N) return null;
        return new Tree() { StaticGraph = graph };
    }
}

partial class Tree
{
    public interface IRerootingOperator<TResult>
    {
        TResult Identity { get; }
        TResult ApplyV(TResult e, int v);
        TResult ApplyE(TResult e, int ei);
        TResult Merge(TResult l, TResult r);
    }

    public (TResult, int edgeIndex)[][] SubTreeValues<TResult, TOperator>(int start, TOperator op = default) where TOperator : struct, IRerootingOperator<TResult>
    {
        var g = StaticGraph;
        var n = g.N;
        var res = new (TResult, int)[n][];
        TResult SubTreeValue(int v, int prev)
        {
            var merged = op.Identity;
            var l = g.Adjacencies(v);
            var c = l.Length;
            var r = new (TResult, int)[c];
            for (var i = 0; i < c; i++)
            {
                var (next, ei) = l[i];
                if (next == prev) continue;
                var subTreeValue = op.ApplyE(SubTreeValue(next, v), ei);
                r[i] = (subTreeValue, ei);
                merged = op.Merge(merged, subTreeValue);
            }
            res[v] = r;
            return op.ApplyV(merged, v);
        }
        SubTreeValue(start, -1);
        return res;
    }

    public TResult[] Rerooting<TResult, TOperator>(TOperator op = default) where TOperator : struct, IRerootingOperator<TResult>
    {
        var g = StaticGraph;
        var n = g.N;
        var res = new TResult[n];
        var subTreeValues = SubTreeValues<TResult, TOperator>(0, op);
        void Evaluate(int v, int prev, TResult prevValue)
        {
            var adjacencies = g.Adjacencies(v);
            var vz = subTreeValues[v];
            var l = adjacencies.Length;
            for (var i = 0; i < l; i++) if (adjacencies[i].next == prev)
            {
                vz[i].Item1 = prevValue;
                break;
            }
            var sumL = new TResult[l];
            var sumR = new TResult[l];
            sumL[0] = op.Identity;
            sumR[l - 1] = op.Identity;
            for (var i = 1; i < l; i++) sumL[i] = op.Merge(sumL[i - 1], vz[i - 1].Item1);
            for (var i = l - 2; i >= 0; i--) sumR[i] = op.Merge(sumR[i + 1], vz[i + 1].Item1);
            res[v] = op.ApplyV(op.Merge(sumR[0], vz[0].Item1), v);
            for (var i = 0; i < l; i++)
            {
                var (next, ei) = adjacencies[i];
                if (next == prev) continue;
                var merged = op.Merge(sumL[i], sumR[i]);
                Evaluate(next, v, op.ApplyE(op.ApplyV(merged, v), ei));
            }
        }
        Evaluate(0, -1, op.Identity);
        return res;
    }
}
0