結果

問題 No.2638 Initial fare
ユーザー titiatitia
提出日時 2024-02-20 04:48:00
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,056 bytes
コンパイル時間 260 ms
コンパイル使用メモリ 11,904 KB
実行使用メモリ 91,544 KB
最終ジャッジ日時 2024-03-22 01:03:37
合計ジャッジ時間 12,139 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
10,112 KB
testcase_01 AC 29 ms
10,112 KB
testcase_02 AC 29 ms
10,112 KB
testcase_03 AC 30 ms
10,112 KB
testcase_04 AC 1,689 ms
82,176 KB
testcase_05 AC 1,863 ms
86,016 KB
testcase_06 AC 31 ms
10,112 KB
testcase_07 AC 1,627 ms
84,744 KB
testcase_08 AC 1,646 ms
79,016 KB
testcase_09 TLE -
testcase_10 AC 1,587 ms
85,424 KB
testcase_11 AC 36 ms
10,112 KB
testcase_12 AC 1,756 ms
83,712 KB
testcase_13 AC 1,357 ms
75,508 KB
testcase_14 AC 1,655 ms
84,608 KB
testcase_15 AC 1,597 ms
85,588 KB
testcase_16 AC 32 ms
10,112 KB
testcase_17 AC 1,659 ms
82,596 KB
testcase_18 AC 1,533 ms
81,420 KB
testcase_19 AC 1,715 ms
82,972 KB
testcase_20 AC 1,733 ms
82,816 KB
testcase_21 AC 1,717 ms
82,276 KB
testcase_22 AC 32 ms
10,112 KB
testcase_23 AC 1,910 ms
86,144 KB
testcase_24 TLE -
testcase_25 AC 32 ms
10,112 KB
testcase_26 AC 1,976 ms
86,272 KB
testcase_27 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

N=int(input())
E=[[] for i in range(N)]

for i in range(N-1):
    x,y=map(int,input().split())
    x-=1
    y-=1
    E[x].append(y)
    E[y].append(x)
    
# 木のHL分解+LCA

ROOT=0

QUE=[ROOT] 
Parent=[-1]*N
Parent[ROOT]=N # ROOTの親を定めておく.
Child=[[] for i in range(N)]
TOP_SORT=[] # トポロジカルソート

while QUE: # トポロジカルソートと同時に親を見つける
    x=QUE.pop()
    TOP_SORT.append(x)
    for to in E[x]:
        if Parent[to]==-1:
            Parent[to]=x
            Child[x].append(to)
            QUE.append(to)

Childs=[[0,0,0] for i in range(N)]

for x in TOP_SORT[::-1]:
    if Child[x]==[]:
        continue

    for c in Child[x]:
        Childs[x][0]+=1
        Childs[x][1]+=Childs[c][0]
        Childs[x][2]+=Childs[c][1]

ANS=0
for i in range(N):
    ANS+=Childs[i][0]+Childs[i][1]+Childs[i][2]

    SUM1=Childs[i][0]
    SUM2=Childs[i][1]

    for c in Child[i]:
        SUM1-=1
        ANS+=SUM1

        ANS+=SUM2-Childs[c][0]

print(ANS)
0