結果

問題 No.1507 Road Blocked
コンテスト
ユーザー kakel-san
提出日時 2024-06-16 22:58:16
言語 C#
(.NET 10.0.102)
コンパイル:
dotnet_c
実行:
/usr/bin/dotnet_wrap
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,722 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,072 ms
コンパイル使用メモリ 150,144 KB
最終ジャッジ日時 2026-03-06 03:40:44
合計ジャッジ時間 3,577 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
Process terminated.
Failed to create the thread pool Gate thread.
   at System.Environment.FailFast(System.Runtime.CompilerServices.StackCrawlMarkHandle, System.String, System.Runtime.CompilerServices.ObjectHandleOnStack, System.String)
   at System.Environment.FailFast(System.Threading.StackCrawlMark ByRef, System.String, System.Exception, System.String)
   at System.Environment.FailFast(System.String, System.Exception)
   at System.Threading.PortableThreadPool+GateThread.CreateGateThread()
   at System.Threading.PortableThreadPool+GateThread.EnsureRunningSlow(System.Threading.PortableThreadPool)
   at System.Threading.ThreadPoolWorkQueue.Dispatch()
   at System.Threading.PortableThreadPool+WorkerThread.WorkerThreadStart()
   at System.Threading.Thread.StartCallback()
System.OutOfMemoryException: Exception of type 'System.OutOfMemoryException' was thrown.
   at System.Threading.Thread.StartCore()
   at System.Threading.PortableThreadPool.GateThread.CreateGateThread()Aborted (core dumped)
/home/judge/.dotnet/sdk/10.0.103/Sdks/Microsoft.NET.Sdk/targets/Microsoft.PackageDependencyResolution.targets(266,5): error NETSDK1004: 資産ファイル '/home/judge/data/code/obj/project.assets.json' が見つかりません。NuGet パッケージの復元を実行して、このファイルを生成してください。 [/home/judge/data/code/main.csproj]

ソースコード

diff #
raw source code 

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static int NN => int.Parse(ReadLine());
    static int[] NMi => ReadLine().Split().Select(c => int.Parse(c) - 1).ToArray();
    static int[][] NMap(int n) => Enumerable.Repeat(0, n).Select(_ => NMi).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var n = NN;
        var map = NMap(n - 1);
        var tree = new List<int>[n];
        for (var i = 0; i < n; ++i) tree[i] = new List<int>();
        foreach (var edge in map)
        {
            tree[edge[0]].Add(edge[1]);
            tree[edge[1]].Add(edge[0]);
        }
        var ans = 0L;
        DFS(n, 0, -1, tree, ref ans);
        var mod = 998_244_353;
        ans %= mod;
        var all = (long)n * (n - 1) / 2 % mod * (n - 1) % mod;
        WriteLine((all - ans + mod) % mod * Exp(all, mod - 2, mod) % mod);
    }
    static int DFS(int n, int cur, int prev, List<int>[] tree, ref long ans)
    {
        var count = 1;
        foreach (var next in tree[cur])
        {
            if (prev == next) continue;
            var num = DFS(n, next, cur, tree, ref ans);
            ans += (long)num * (n - num);
            count += num;
        }
        return count;
    }
    static long Exp(long n, long p, int mod)
    {
        long _n = n % mod;
        var _p = p;
        var result = 1L;
        if ((_p & 1) == 1) result *= _n;
        while (_p > 0)
        {
            _n = _n * _n % mod;
            _p >>= 1;
            if ((_p & 1) == 1) result = result * _n % mod;
        }
        return result;
    }
}
0