結果

問題 No.2638 Initial fare
コンテスト
ユーザー flippergo
提出日時 2025-02-22 11:07:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 799 bytes
コンパイル時間 362 ms
コンパイル使用メモリ 82,252 KB
実行使用メモリ 564,676 KB
最終ジャッジ日時 2025-02-22 11:07:31
合計ジャッジ時間 11,134 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 TLE * 2 MLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = int(input())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    u,v = map(int,input().split())
    G[u].append(v)
    G[v].append(u)
box = set()
def f(i,pi,n):
    if n==1:
        if pi in G[i]:
            for j in G[i]:
                if j==pi:continue
                box.add(j)
        else:
            for j in G[i]:
                box.add(j)
        return
    for j in G[i]:
        if j==pi:continue
        f(j,i,n-1)
ans = set()
def dfs(i,pi,n):
    box.clear()
    f(i,0,n)
    for j in box:
        if i<j:
            ans.add((i,j))
        else:
            ans.add((j,i))
    for j in G[i]:
        if j==pi:continue
        dfs(j,i,n)
for i in range(1,N+1):
    if len(G[i])==1:
        ini = i
        break
for n in range(2,3+1):
    dfs(ini,0,n)
print(len(ans)+N-1)
0