結果

問題 No.3346 Tree to DAG
コンテスト
ユーザー n_bitand_n_per_3
提出日時 2025-10-31 09:12:04
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,931 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 112,064 KB
最終ジャッジ日時 2025-11-13 21:09:58
合計ジャッジ時間 9,938 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 28 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
MOD = 998244353

N = int(input())

degrees = [0]*N
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)
  degrees[u] += 1
  degrees[v] += 1


q = deque([0])
visited = [False]*N
visited[0] = True
dist = [0]*N
while q:
  v = q.popleft()
  for u in connect[v]:
    if not visited[u]:
      q.append(u)
      visited[u] = True
      dist[u] = dist[v] + 1
  
a = max(range(N),key=lambda x:dist[x])


q = deque([a])
visited = [False]*N
visited[a] = True
dist = [0]*N
while q:
  v = q.popleft()
  for u in connect[v]:
    if not visited[u]:
      q.append(u)
      visited[u] = True
      dist[u] = dist[v] + 1

b = max(range(N),key=lambda x:dist[x])

d = dist[b]
v = b
path = [b]
while d >= 0:
  for u in connect[v]:
    if dist[u] == d-1:
      path.append(u)
      d -= 1
      v = u
      break
  else:
    break

q = deque(path)
visited = [False]*N
for i in path:
  visited[i] = True
dist = [0]*N
while q:
  v = q.popleft()
  for u in connect[v]:
    if not visited[u]:
      q.append(u)
      visited[u] = True
      dist[u] = dist[v] + 1

#print(dist)
c = max(range(N),key=lambda x:dist[x] if x != a and x != b else -1)

#print(a,b,c)

S = set(path)
q = deque([c])
visited = [False]*N
visited[c] = True
dist = [0]*N
while q:
  v = q.popleft()
  if v in S:
    F = v
    q = deque([])
    break
  for u in connect[v]:
    if not visited[u]:
      q.append(u)
      visited[u] = True
      dist[u] = dist[v] + 1

#print(F)

q = deque([F])
visited = [False]*N
visited[F] = True
dist = [0]*N
while q:
  v = q.popleft()
  for u in connect[v]:
    if not visited[u]:
      q.append(u)
      visited[u] = True
      dist[u] = dist[v] + 1

x,y,z = dist[a],dist[b],dist[c]
K = x+y+z
#print(x,y,z)

ans = pow(2,N+2,MOD) - pow(2,N-K,MOD) * (pow(2,x+1,MOD) + pow(2,y+1,MOD) + pow(2,z+1,MOD) - 3)
ans %= MOD

print(ans)
0