結果

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

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
in01.txt AC 114 ms
67,316 KB
in02.txt AC 111 ms
67,308 KB
in03.txt AC 104 ms
67,316 KB
in04.txt AC 104 ms
67,316 KB
in05.txt AC 104 ms
68,316 KB
in06.txt AC 105 ms
68,572 KB
in07.txt AC 105 ms
67,308 KB
in08.txt AC 104 ms
67,312 KB
r01.txt AC 104 ms
68,380 KB
r02.txt AC 105 ms
67,420 KB
r03.txt AC 106 ms
67,308 KB
r04.txt AC 115 ms
67,300 KB
r05.txt AC 122 ms
67,308 KB
r06.txt AC 107 ms
67,844 KB
r07.txt AC 111 ms
68,640 KB
r08.txt AC 143 ms
69,132 KB
r09.txt AC 157 ms
70,564 KB
r10.txt AC 146 ms
69,764 KB
r11.txt AC 369 ms
79,616 KB
r12.txt AC 379 ms
79,408 KB
r13.txt AC 460 ms
83,720 KB
r14.txt AC 229 ms
74,488 KB
r15.txt AC 236 ms
74,112 KB
z01.txt RE -
z02.txt RE -
z03.txt AC 367 ms
87,268 KB
z04.txt AC 362 ms
91,468 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