結果
問題 | No.2638 Initial fare |
ユーザー | timi |
提出日時 | 2024-02-19 21:51:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 581 ms / 2,000 ms |
コード長 | 627 bytes |
コンパイル時間 | 392 ms |
コンパイル使用メモリ | 82,260 KB |
実行使用メモリ | 143,932 KB |
最終ジャッジ日時 | 2024-09-29 01:50:05 |
合計ジャッジ時間 | 10,658 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
01_ | AC * 3 |
other | AC * 25 |
ソースコード
N=int(input())D=[[] for i in range(N)]for i in range(N-1):x,y=map(int, input().split())x-=1;y-=1D[x].append(y)D[y].append(x)ans=N-1from collections import dequed=deque()V=[-1]*NV[0]=0d.append(0)G=[[] for i in range(N)]P=[-1]*Nwhile d:now=d.popleft()for nex in D[now]:if V[nex]==-1:G[now].append(nex)V[nex]=V[now]+1P[nex]=nowd.append(nex)DD={}for v in V:if v not in DD:DD[v]=0DD[v]+=1for i in range(N):g=len(G[i])if i!=0:ans+=gans+=g*(g-1)//2if V[i]>=2:c=P[P[i]]ans+=len(G[c])-1if V[i]>=3:ans+=1print(ans)