結果

問題 No.3346 Tree to DAG
コンテスト
ユーザー Nzt3
提出日時 2025-11-12 16:43:17
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,561 bytes
コンパイル時間 194 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 109,444 KB
最終ジャッジ日時 2025-11-13 21:22:00
合計ジャッジ時間 8,867 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 答えを陽に持つ TLE

def bfs(G, N, start):
    par = [-1] * N
    look = []
    for s in start:
        par[s] = s
        look.append(s)
    l = 0
    while l < len(look):
        v = look[l]
        l += 1
        for u in G[v]:
            if par[u] == -1:
                par[u] = v
                look.append(u)
    return look, par


def main():
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline

    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        U, V = map(int, input().split())
        U -= 1
        V -= 1
        G[U].append(V)
        G[V].append(U)

    # 1. BFS from node 0
    dist, par = bfs(G, N, [0])
    d1 = dist[-1]
    # 2. BFS from farthest node
    dist, par = bfs(G, N, [d1])
    d2 = dist[-1]

    # 3. Recover diameter path
    diameter = []
    t = d2
    while True:
        diameter.append(t)
        if par[t] == t:
            break
        t = par[t]

    # 4. BFS from all diameter nodes
    dist, par = bfs(G, N, diameter)

    # 5. Compute depth array (max depth from each node)
    depth = [0] * N
    for i in reversed(dist):
        if par[i] != i:
            depth[par[i]] = max(depth[par[i]], depth[i] + 1)
        else:
            break

    ans = 0
    t = 0
    for i in diameter:
        a, b, c = t, len(diameter)-1-t, depth[i]
        K = a+b+c
        now = 2**(N+2) - 2**(N-K)*(2**(a+1)+2**(b+1)+2**(c+1)-3)
        if ans < now:
            ans = now
        t += 1

    print(ans % 998244353)


if __name__ == "__main__":
    main()
0