結果

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

ソースコード

diff # 

# 答えを陽に持つ
from collections import deque
from collections import Counter


class TopK:
    def __init__(self, K, e):
        self.array = [e]*K
        self._index = 0
        self.K = K
        self.e = e

    def add(self, x):
        for i in range(self.K):
            if x >= self.array[i]:
                self.array = self.array[:i] + [x] + self.array[i:-1]
                break

    def __str__(self):
        return str(self.array)


# ===================================
MOD = 998244353

N = int(input())

connect = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(lambda x: int(x)-1, input().split())
    connect[u].append(v)
    connect[v].append(u)

top3_array = [TopK(3, 0) for _ in range(N)]  # ある頂点から見た部分木の中で深さtop3のやつ

# 子から親への頂点を削除 O(M)
parents = [-1] * N
tps = []
Q = deque([0])
while Q:
    i = Q.popleft()
    tps.append(i)
    for a in connect[i]:
        if a != parents[i]:
            parents[a] = i
            connect[a].remove(i)
            Q.append(a)

# print(connect)
# print(parents)
# print(tps)

# Bottom-Up DP
acc_BU = [0] * N
res_BU = [0] * N
for i in tps[1:][::-1]:
    res_BU[i] = acc_BU[i] + 1
    p = parents[i]
    acc_BU[p] = max(acc_BU[p], res_BU[i])
    top3_array[p].add(res_BU[i])
res_BU[tps[0]] = acc_BU[tps[0]] + 1

# print(res_BU)
# print([x.array for x in top3_array])

# Top-Down DP
acc_TD = [0] * N
res_TD = [0] * N
res = [0]*N

# 1. 初期化の修正
res_TD[0] = 0  # 根の「親側」の深さは0
res[0] = max(res_BU[0], res_TD[0])  # 根の最大深さ
top3_array[0].add(res_TD[0])  # 根のtop3にも親側(0)を追加

for i in tps:
    # 2. array の構築を修正
    # 子のBU深さリスト + 親側(TD)の深さ
    array = [res_BU[c] for c in connect[i]]
    array.append(res_TD[i])  # res[parents[i]] ではなく res_TD[i]

    # print("Debug",i,parents[i],array) # デバッグ用
    L = len(array)

    # 右向き累積max (左からi-1番目までのmax)
    accr_cum = [-float("inf")]*(len(array)+1)
    for j, v in enumerate(array):
        accr_cum[j+1] = max(accr_cum[j], v)

    # 左向き累積max (右からi+1番目までのmax)
    accl_cum = [-float("inf")]*(len(array)+1)
    for j, v in enumerate(reversed(array)):
        accl_cum[L-j-1] = max(v, accl_cum[L-j])

    # print(accr_cum, accl_cum) # デバッグ用

    # 3. acc_TD, res_TD の更新ロジックを修正
    for j, c in enumerate(connect[i]):
        # c 以外の方向の最大深さを計算
        # (arrayのj番目が c のBU深さ だった)
        acc_TD_for_c = max(accr_cum[j], accl_cum[j+1])

        # c にとっての「親側(i)からの深さ」は acc_TD_for_c + 1
        res_TD[c] = acc_TD_for_c + 1

        # c の最大深さ（偏心度）を更新
        res[c] = max(res_BU[c], res_TD[c])

        # c のtop3に「親側からの深さ」を追加
        top3_array[c].add(res_TD[c])
        # print("add",j,c,res[c],top3_array[c]) # デバッグ用


def f(t):
    a, b, c = t
    K = a+b+c
    return 2**(N+2) - 2**(N-K)*(2**(a+1) + 2**(b+1) + 2**(c+1) - 3)


ans = 0
for i in range(N):
    x = f(top3_array[i].array)
    if ans < x:
        ans = x

print(ans % 998244353)
0