#503715 (PyPy3) No.1098 LCAs

• 問題: No.1098 LCAs
• ユーザー: uni_python
• 提出日時: 2020-06-26 23:33:47
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 894 ms / 2,000 ms
• コード長: 1,286 bytes
• コンパイル時間: 144 ms
• コンパイル使用メモリ: 82,420 KB
• 実行使用メモリ: 153,660 KB
• 最終ジャッジ日時: 2024-07-05 00:22:11
• 合計ジャッジ時間: 14,064 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 28

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import sys
input=sys.stdin.readline
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def main():
    mod=10**9+7
    N=I()
    if N==1:
        print(1)
        exit()
    
    adj=[[]for _ in range(N)]
    
    for i in range(N-1):
        v,w=MI()
        v-=1
        w-=1
        adj[v].append(w)
        adj[w].append(v)
        
    
    import queue
    D=[[]for _ in range(N)]
    q=queue.Queue()
    q.put((0,-1,0))
    used=[0]*N
    used[0]=1
    D[0].append(0)
    
    while not q.empty():
        v,p,d=q.get()
        for nv in adj[v]:
            if used[nv]==0:
                q.put((nv,v,d+1))
                used[nv]=1
                D[d+1].append(nv)
            
                
    anss=[[0,0]for _ in range(N)]#答え，部分木のサイズ
    #親は自動で０になる
    
    for i in range(N-1,-1,-1):
        for v in D[i]:
            s=1
            temp=0#子のサイズの2乗の合計
            for nv in adj[v]:
                s+=anss[nv][1]
                temp+=anss[nv][1]**2
            
            anss[v][1]=s
            anss[v][0]=s*s-temp
        
    for i in range(N):
        print(anss[i][0])
            
                
        
    
    
main()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX