結果

問題 No.439 チワワのなる木
ユーザー ckawatak
提出日時 2018-03-29 00:00:52
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 841 bytes
コンパイル時間 617 ms
コンパイル使用メモリ 82,452 KB
実行使用メモリ 93,692 KB
最終ジャッジ日時 2024-06-25 13:54:47
合計ジャッジ時間 5,757 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25 RE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = int(input())
S = input()
G = [ [] for _ in range(len(S))]

for i in range(N-1):
    a,b = sorted(list(map(int, input().split(' '))))
    G[a-1].append(b-1)
    G[b-1].append(a-1)

tc = 0
tw = 0
for s in S:
    if s == 'c':
        tc += 1
    else:
        tw += 1

cc = [0 for _ in range(len(S))]
cw = [0 for _ in range(len(S))]
count = 0

def dfs(current, parent):
    global count
    if S[current] == 'c':
        cc[current] += 1
    else:
        cw[current] += 1

    for adj in G[current]:
        if adj != parent:
            dfs(adj, current)
            cc[current] += cc[adj]
            cw[current] += cw[adj]
            if S[current] == 'w':
                count += cc[adj] * (tw-1-cw[adj])

    if parent != -1 and S[current] == 'w':
        count += (tc-cc[current]) * (cw[current]-1)
        
dfs(0, -1)
print(count)
0