結果
問題 | No.1507 Road Blocked |
ユーザー | marroncastle |
提出日時 | 2021-05-14 22:49:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 601 ms / 2,000 ms |
コード長 | 1,723 bytes |
コンパイル時間 | 393 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 162,688 KB |
最終ジャッジ日時 | 2024-10-02 03:14:46 |
合計ジャッジ時間 | 19,443 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 44 ms
54,016 KB |
testcase_01 | AC | 47 ms
53,504 KB |
testcase_02 | AC | 47 ms
53,760 KB |
testcase_03 | AC | 275 ms
162,688 KB |
testcase_04 | AC | 582 ms
162,048 KB |
testcase_05 | AC | 562 ms
162,176 KB |
testcase_06 | AC | 573 ms
159,360 KB |
testcase_07 | AC | 591 ms
161,536 KB |
testcase_08 | AC | 572 ms
161,920 KB |
testcase_09 | AC | 588 ms
162,560 KB |
testcase_10 | AC | 574 ms
162,304 KB |
testcase_11 | AC | 571 ms
161,408 KB |
testcase_12 | AC | 588 ms
161,536 KB |
testcase_13 | AC | 579 ms
161,792 KB |
testcase_14 | AC | 583 ms
161,792 KB |
testcase_15 | AC | 581 ms
162,432 KB |
testcase_16 | AC | 576 ms
162,048 KB |
testcase_17 | AC | 587 ms
161,536 KB |
testcase_18 | AC | 580 ms
162,688 KB |
testcase_19 | AC | 564 ms
162,176 KB |
testcase_20 | AC | 568 ms
162,304 KB |
testcase_21 | AC | 566 ms
161,920 KB |
testcase_22 | AC | 570 ms
161,920 KB |
testcase_23 | AC | 582 ms
161,664 KB |
testcase_24 | AC | 601 ms
161,664 KB |
testcase_25 | AC | 590 ms
162,560 KB |
testcase_26 | AC | 585 ms
162,176 KB |
testcase_27 | AC | 580 ms
162,432 KB |
testcase_28 | AC | 576 ms
162,304 KB |
testcase_29 | AC | 583 ms
162,304 KB |
testcase_30 | AC | 577 ms
161,536 KB |
testcase_31 | AC | 579 ms
161,792 KB |
testcase_32 | AC | 582 ms
161,920 KB |
ソースコード
import sysinput = sys.stdin.readlinefrom collections import dequeclass Tree:def __init__(self, N):self.V = Nself.edge2 = [[] for _ in range(N)]self.edge = [deque([]) for _ in range(N)]self.order = []def add_edges(self, ind=1, bi=True):for i in range(self.V-1):a,b = map(int, input().split())a -= ind; b -= indself.edge[a].append(b)self.edge2[a].append(b)if bi:self.edge[b].append(a)self.edge2[b].append(a)def add_edge(self, a, b, bi=True):self.edge[a].append(b)if bi: self.edge[b].append(a)def dp(self, start):stack = deque([start])self.parent = [self.V]*self.V; self.parent[start] = -1self.order.append(start)#記録したい値の配列を定義self.dp = [1]*self.Vwhile stack:v = stack[-1]while len(self.edge[v]):u = self.edge[v].popleft()if u==self.parent[v]: continueself.parent[u]=vstack.append(u); self.order.append(u)breakelse:stack.pop()for v in self.order[::-1]:for u in self.edge2[v]:if u==self.parent[v]: continueself.dp[v] += self.dp[u] #帰りがけ処理def bfs(self, start):d = deque([start])self.min_cost = [-1]*self.V; self.min_cost[start]=0while len(d)>0:v = d.popleft()for w in self.edge[v]:if self.min_cost[w]==-1:self.min_cost[w]=self.min_cost[v]+1d.append(w)returnN = int(input())G = Tree(N)G.add_edges(ind=1, bi=True)G.dp(0)ans = 0MOD = 998244353for i in range(1,N):num = G.dp[i]ans += num*(num-1) + (N-num)*(N-num-1)ans *= pow(N*(N-1)*(N-1), MOD-2, MOD)print(ans%MOD)