結果
問題 | No.2638 Initial fare |
ユーザー |
👑 |
提出日時 | 2024-02-19 21:28:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 433 ms / 2,000 ms |
コード長 | 822 bytes |
コンパイル時間 | 131 ms |
コンパイル使用メモリ | 82,512 KB |
実行使用メモリ | 141,060 KB |
最終ジャッジ日時 | 2024-09-29 01:24:01 |
合計ジャッジ時間 | 8,552 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
n = int(input())edges = [[] for _ in range(n)]for _ in range(n - 1):u, v = map(int, input().split())u -= 1v -= 1edges[u].append(v)edges[v].append(u)route = []stack = []visited = [False] * nstack.append(0)while stack:u = stack.pop()visited[u] = Trueroute.append(u)for v in edges[u]:if not visited[v]:stack.append(v)one = [0] * ntwo = [0] * nthree = [0] * nans = 0for pos in route[::-1]:visited[pos] = Falsefor npos in edges[pos]:if visited[npos]:continueans += 1ans += one[npos]ans += one[pos] * 1ans += two[npos]ans += one[pos] * one[npos]ans += two[pos]one[pos] += 1two[pos] += one[npos]three[pos] += two[npos]print(ans)