結果

問題 No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑
ユーザー tobisatis
提出日時 2025-07-18 23:27:59
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 1,687 ms / 3,000 ms
コード長 7,883 bytes
コンパイル時間 7,970 ms
コンパイル使用メモリ 169,732 KB
実行使用メモリ 281,516 KB
最終ジャッジ日時 2025-07-18 23:28:32
合計ジャッジ時間 31,352 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (104 ミリ秒)。
  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 cd = CentroidDecomposition.Build(tree);
var ll = new int[n][];
for (var i = 0; i < n; i++) ll[i] = new int[sg.Adjacencies(i).Length];
for (var level = 0; level < cd.LevelCount; level++)
{
    foreach (var center in cd.Centroids[level])
    {
        int S(int v, int prev)
        {
            var adji = sg.Adjacencies(v);
            var res = 0;
            if (cd.Levels[v] < level)
            {
                for (var j = 0; j < adji.Length; j++)
                {
                    var (next, _) = adji[j];
                    if (next == prev) continue;
                    res = Math.Max(res, ll[v][j]);
                }
                return res + 1;
            }
            for (var j = 0; j < adji.Length; j++)
            {
                var (next, _) = adji[j];
                if (next == prev) continue;
                var ns = S(next, v);
                if (v == center) ll[center][j] = ns;
                res = Math.Max(res, ns);
            }
            return res + 1;
        }
        S(center, -1);
    }
}
var ans = 0;
foreach (var a in ll)
{
    Array.Sort(a);
    Array.Reverse(a);
    var min = int.MaxValue;
    for (var i = 0; i < a.Length; i++)
    {
        min = Math.Min(a[i], min);
        ans = Math.Max(ans, min * (i + 1) + 1);
    }
}
Console.WriteLine(ans);

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 };
    }
}

class CentroidDecomposition
{
    public int LevelCount { get; private init; }
    // Levels[v] is the level of the tree where v is the centroid
    public required int[] Levels { get; init; }
    // Centroid[level] is the list of centroids at the level
    public required List<int>[] Centroids { get; init; }
    // Roots[level][v] is the root of the tree of the level that has v
    public required int[][] Roots { get; init; }
    // Depths[level][v] is the distance from the root of the tree of the level that has v
    public required int[][] Depths { get; init; }

    public static CentroidDecomposition Build(Tree tree)
    {
        var g = tree.StaticGraph;
        var n = g.N;
        var levels = new int[n];
        for (var i = 0; i < n; i++) levels[i] = -1;
        int FindCentroid(int[] subTreeSizes, int[] parents, int total, int start)
        {
            var centroid = -1;
            int Internal(int v, int prev)
            {
                var size = 1;
                parents[v] = prev;
                var isCentroid = true;
                var adjacencies = g.Adjacencies(v);
                foreach (var (next, _) in adjacencies)
                {
                    if (next == prev || levels[next] >= 0) continue;
                    var cs = Internal(next, v);
                    if (cs > (total >> 1)) isCentroid = false;
                    size += cs;
                }
                if (isCentroid && size >= total - (total >> 1)) centroid = v;
                return subTreeSizes[v] = size;
            }
            Internal(start, -1);
            return centroid;
        }
        var starts = new List<(int, int)>(){ (0, n) };
        var levelCount = 0;
        while (starts.Count > 0)
        {
            var subTreeSizes = new int[n];
            var parents = new int[n];
            var nextStarts = new List<(int, int)>();
            foreach (var (start, size) in starts)
            {
                var centroid = FindCentroid(subTreeSizes, parents, size, start);
                levels[centroid] = levelCount;
                var parent = parents[centroid];
                var adjacencies = g.Adjacencies(centroid);
                foreach (var (next, _) in adjacencies)
                {
                    if (levels[next] >= 0) continue;
                    var nextSize = subTreeSizes[next];
                    if (next == parent) nextSize = size - subTreeSizes[centroid];
                    nextStarts.Add((next, nextSize));
                }
            }
            starts = nextStarts;
            levelCount++;
        }
        var centroids = new List<int>[levelCount];
        for (var i = 0; i < levelCount; i++) centroids[i] = new();
        for (var i = 0; i < n; i++) centroids[levels[i]].Add(i);
        var roots = new int[levelCount][];
        var depths = new int[levelCount][];
        for (var level = 0; level < levelCount; level++)
        {
            var rs = new int[n];
            var ds = new int[n];
            for (var i = 0; i < n; i++) rs[i] = ds[i] = -1;
            void S(int v, int prev)
            {
                var (r, d) = (rs[v], ds[v] + 1);
                var adjacencies = g.Adjacencies(v);
                foreach (var (next, _) in adjacencies)
                {
                    if (next == prev || levels[next] < level) continue;
                    (rs[next], ds[next]) = (r, d);
                    S(next, v);
                }
            }
            foreach (var centroid in centroids[level])
            {
                rs[centroid] = centroid;
                ds[centroid] = 0;
                S(centroid, -1);
            }
            roots[level] = rs;
            depths[level] = ds;
        }
        return new()
        {
            LevelCount = levelCount,
            Levels = levels,
            Centroids = centroids,
            Roots = roots,
            Depths = depths,
        };
    }
}
0