結果

問題 No.439 チワワのなる木
ユーザー roaris
提出日時 2019-11-09 16:12:29
言語 PyPy3
(7.0.0)
結果
RE   .
実行時間 -
コード長 837 Byte
コンパイル時間 1,344 ms
使用メモリ 113,452 KB
最終ジャッジ日時 2020-01-28 08:22:41

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
in01.txt AC 112 ms
78,484 KB
in02.txt AC 108 ms
78,184 KB
in03.txt AC 116 ms
78,372 KB
in04.txt AC 108 ms
78,464 KB
in05.txt AC 112 ms
78,492 KB
in06.txt AC 112 ms
78,620 KB
in07.txt AC 112 ms
78,416 KB
in08.txt AC 112 ms
78,204 KB
r01.txt AC 112 ms
78,288 KB
r02.txt AC 112 ms
78,208 KB
r03.txt AC 112 ms
78,620 KB
r04.txt AC 112 ms
78,184 KB
r05.txt AC 112 ms
78,340 KB
r06.txt AC 120 ms
78,352 KB
r07.txt AC 136 ms
78,492 KB
r08.txt AC 156 ms
80,320 KB
r09.txt AC 180 ms
80,768 KB
r10.txt AC 168 ms
80,452 KB
r11.txt AC 392 ms
90,496 KB
r12.txt AC 352 ms
89,388 KB
r13.txt AC 456 ms
93,500 KB
r14.txt AC 244 ms
84,756 KB
r15.txt AC 248 ms
84,844 KB
z01.txt RE -
z02.txt RE -
z03.txt AC 392 ms
98,272 KB
z04.txt AC 380 ms
102,024 KB
z05.txt RE -
テストケース一括ダウンロード

ソースコード

diff #
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(cur, prev=-1):
    global res
    
    cs = []
    ws = []
    
    for nn in adj_list[cur]:
        if nn != prev:
            c, w = dfs(nn, cur)
            cs.append(c)
            ws.append(w)
    
    if S[cur] == 'c':
        return sum(cs)+1, sum(ws)
    elif S[cur] == 'w':
        cs.append(total_c-sum(cs))
        ws.append(total_w-sum(ws)-1)
        sum_w = sum(ws)
        
        for c, w in zip(cs, ws):
            res += c*(sum_w-w)
        
        return sum(cs[:-1]), sum_w-ws[-1]+1

N = int(input())
S = input()
total_c = S.count('c')
total_w = S.count('w')
adj_list = [[] for _ in range(N)]

for _ in range(N-1):
    a, b = map(int, input().split())
    adj_list[a-1].append(b-1)
    adj_list[b-1].append(a-1)

res = 0
dfs(0)

print(res)
0