結果

問題 No.439 チワワのなる木
ユーザー one0803
提出日時 2019-11-09 16:14:29
言語 Python3
(3.7.4 + numpy 1.14.5 + scipy 1.1.0)
結果
AC  
実行時間 716 ms
コード長 837 Byte
コンパイル時間 61 ms
使用メモリ 165,872 KB
最終ジャッジ日時 2019-11-09 16:14:35

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
in01.txt AC 18 ms
6,872 KB
in02.txt AC 18 ms
6,876 KB
in03.txt AC 18 ms
6,872 KB
in04.txt AC 19 ms
6,872 KB
in05.txt AC 18 ms
6,872 KB
in06.txt AC 18 ms
6,876 KB
in07.txt AC 18 ms
6,872 KB
in08.txt AC 18 ms
6,876 KB
r01.txt AC 18 ms
6,876 KB
r02.txt AC 18 ms
6,876 KB
r03.txt AC 18 ms
6,876 KB
r04.txt AC 19 ms
6,872 KB
r05.txt AC 19 ms
6,876 KB
r06.txt AC 19 ms
8,916 KB
r07.txt AC 20 ms
6,876 KB
r08.txt AC 23 ms
8,924 KB
r09.txt AC 26 ms
6,876 KB
r10.txt AC 24 ms
6,876 KB
r11.txt AC 390 ms
18,848 KB
r12.txt AC 346 ms
18,460 KB
r13.txt AC 447 ms
22,892 KB
r14.txt AC 133 ms
11,180 KB
r15.txt AC 121 ms
10,028 KB
z01.txt AC 582 ms
37,164 KB
z02.txt AC 716 ms
142,236 KB
z03.txt AC 549 ms
24,492 KB
z04.txt AC 430 ms
23,948 KB
z05.txt AC 666 ms
165,872 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