結果
問題 | No.2638 Initial fare |
ユーザー |
|
提出日時 | 2024-02-19 21:39:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,219 ms / 2,000 ms |
コード長 | 1,080 bytes |
コンパイル時間 | 262 ms |
コンパイル使用メモリ | 81,964 KB |
実行使用メモリ | 182,328 KB |
最終ジャッジ日時 | 2024-10-02 13:14:57 |
合計ジャッジ時間 | 19,099 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
import sysinput = lambda :sys.stdin.readline()[:-1]ni = lambda :int(input())na = lambda :list(map(int,input().split()))yes = lambda :print("yes");Yes = lambda :print("Yes")no = lambda :print("no");No = lambda :print("No")#######################################################################n = ni()g = [[] for i in range(n)]for i in range(n-1):a,b = na()g[a-1].append(b-1)g[b-1].append(a-1)dp = [[1,0,0,0] for i in range(n)]seen = [0]*nq = [0]et = []seen[0] = 1p = [-1] * nchi = [[] for i in range(n)]while q:x = q.pop()et.append(x)for y in g[x]:if seen[y]:continueseen[y] = 1p[y] = xchi[x].append(y)q.append(y)for x in et[::-1]:for y in chi[x]:dp[x][1] += dp[y][0]dp[x][2] += dp[y][1]dp[x][3] += dp[y][2]ans = 0for i in range(n):x = it = 3s = sum(dp[x])while p[x] != -1 and t:y = xx = p[x]s += sum(dp[x][:t]) - sum(dp[y][:t-1])t -= 1ans += s#print(s)print((ans-n)//2)