結果

問題 No.439 チワワのなる木
ユーザー roaris
提出日時 2019-11-09 16:14:29
言語 Python3
(3.8.2 + numpy 1.14.5 + scipy 1.1.0)
結果
AC  
実行時間 656 ms / 5,000 ms
コード長 837 Byte
コンパイル時間 49 ms
使用メモリ 152,280 KB
最終ジャッジ日時 2020-05-14 13:13:29

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 17 ms
5,648 KB
testcase_01 AC 17 ms
5,648 KB
testcase_02 AC 18 ms
5,648 KB
testcase_03 AC 18 ms
5,644 KB
testcase_04 AC 17 ms
5,648 KB
testcase_05 AC 17 ms
5,648 KB
testcase_06 AC 17 ms
5,648 KB
testcase_07 AC 18 ms
5,644 KB
testcase_08 AC 17 ms
5,652 KB
testcase_09 AC 17 ms
5,648 KB
testcase_10 AC 18 ms
5,648 KB
testcase_11 AC 17 ms
5,644 KB
testcase_12 AC 17 ms
5,644 KB
testcase_13 AC 17 ms
5,648 KB
testcase_14 AC 18 ms
5,648 KB
testcase_15 AC 21 ms
5,748 KB
testcase_16 AC 24 ms
5,748 KB
testcase_17 AC 22 ms
5,752 KB
testcase_18 AC 328 ms
17,832 KB
testcase_19 AC 310 ms
17,284 KB
testcase_20 AC 442 ms
21,376 KB
testcase_21 AC 131 ms
10,744 KB
testcase_22 AC 117 ms
9,940 KB
testcase_23 AC 501 ms
34,284 KB
testcase_24 AC 656 ms
130,552 KB
testcase_25 AC 452 ms
22,852 KB
testcase_26 AC 396 ms
22,356 KB
testcase_27 AC 552 ms
152,280 KB
権限があれば一括ダウンロードができます

ソースコード

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