結果
問題 |
No.1098 LCAs
|
ユーザー |
|
提出日時 | 2022-08-29 20:30:42 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,709 ms / 2,000 ms |
コード長 | 628 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 12,416 KB |
実行使用メモリ | 87,808 KB |
最終ジャッジ日時 | 2024-11-29 02:13:54 |
合計ジャッジ時間 | 22,219 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
import sys sys.setrecursionlimit(10**7) n = int(input()) vw = [[] for i in range(n)] for i in range(n-1): v,w = map(int,input().split()) v -= 1 w -= 1 vw[v].append(w) vw[w].append(v) dp = [0]*n chk = [0]*n ans = [0]*n def dfs(v,pre): if chk[v] == 1: return dp[v] tmp = 1 rui2 = 0 for i in range(len(vw[v])): if vw[v][i] == pre: continue t = dfs(vw[v][i],v) dp[v] += t tmp += t rui2 += t**2 chk[v] = 1 dp[v] += 1 ans[v] = tmp**2-rui2 return dp[v] dfs(0,-1) #print(dp) print(*ans,sep="\n") #for i in range(n):