[WEEK03] 20일차. 아침 산책

21606 아침 산책

혼자서 아이디어가 떠오르지 않아서 다른 분의 풀이를 참고했다..

해당 블로그

# 실외 점에 실내 점 N개가 붙어있을 때 경로의 수 = N * 1(중간 실외 점) * (N-1) = N*(N-1).
# 실외 점 두개 붙어있을 땐 서로를 시작점 끝점으로 경로 2가지.

from sys import setrecursionlimit, stdin
setrecursionlimit(10**9)
def dfs(v, cnt): # v: 정점 번호 & cnt: 실외 점에 붙은 실내 점 개수
    
    visited[v] = 1
    
    for i in graph[v]: # 노드 v와 붙어있는 점을 하나씩 불러온다.
        if indoor[i]:  # 해당 점이 실내 점이면
            cnt += 1 # 실내 점 개수 +1
        elif not visited[i] and not indoor[i]: # 해당 점이 실외 점이고 첫 방문,
            cnt = dfs(i, cnt) # 해당 실외 점 기준으로 dfs
    return cnt

input = stdin.readline
N = int(input())

indoor = [0] + list(map(int, input().rstrip())) # 실내 여부. 노드 인덱스 번호 1부터 시작하기 위해 앞에 0

graph = [[] for _ in range(N+1)]

ans = 0
for _ in range(N-1): # 셋째 줄부터 N+1번 줄까지
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    if indoor[a] and indoor[b]: # 둘다 실내일 때,
        ans += 2 # 서로를 시작점 끝점으로 하는 경우 2가지 ans에 더함.

visited = [0] * (N+1)
for i in range(1, N+1):
    if not visited[i] and not indoor[i]: # 첫 방문 & 실외 점이면,
        in_cnt = dfs(i, 0)
        ans += in_cnt*(in_cnt-1)  # 붙어있는 실내 점 개수 in_cnt일 때 경우의 수 ans에 더함.

print(ans)