자전거가 닿는 구역

문제

공유 자전거 관리 구역에는 1번부터 N번까지 번호가 붙은 대여소가 있다. 대여소 사이에는 양방향 골목 N−1개가 있으며, 어느 대여소에서 출발해도 모든 대여소에 갈 수 있다. 골목 하나를 지나는 데 필요한 거리는 1이다. 일부 대여소에는 이용 가능한 자전거가 한 대 이상 있고, 나머지 대여소에는 자전거가 없다. 조사하는 동안 자전거의 위치는 바뀌지 않는다. 운영자는 정수 k에 대해 안내 범위가 k인 지도를 만든다. 어떤 대여소에서 거리가 k 이하인 곳에 자전거가 있는 대여소가 하나라도 있으면, 그 대여소를 지도에서 활성 대여소로 표시한다. 이 거리를 계산할 때는 활성 여부와 관계없이 모든 대여소와 골목을 이용한다. 자전거가 있는 대여소는 k가 0이어도 활성이다. 자전거가 구역 전체에 한 대도 없으면 활성 대여소도 없다. 서로 다른 두 대여소가 모두 활성이고, 두 대여소를 잇는 경로에 있는 모든 대여소도 활성이라면 두 대여소를 하나의 연결 가능한 쌍으로 센다. 쌍에는 순서가 없으므로 같은 두 대여소를 반대 순서로 다시 세지 않는다. 운영자는 k가 0부터 N−1까지 변할 때 연결 가능한 쌍이 몇 개인지 모두 알고 싶다. 골목 구조와 자전거 보유 여부는 길이 2N인 문자열로 주어진다. 문자열은 한 대여소의 방문 시작 문자, 그 대여소의 각 자식에 대한 문자열, 방문 종료 문자 순서로 구성된다. 방문 시작 문자는 자전거가 있으면 B, 없으면 E이고, 방문 종료 문자는 )이다. 가장 바깥 대여소가 루트이며, 방문 시작 문자가 등장하는 순서대로 대여소 번호를 붙인다. 각 대여소는 자신의 바로 바깥 대여소와 골목으로 연결된다. 주어진 문자열은 항상 하나의 올바른 트리를 나타낸다.

입력

첫째 줄에 대여소 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 200,000이다.
둘째 줄에 B, E, )로만 이루어진 길이 2N의 문자열 S가 주어진다. B와 E는 합쳐서 정확히 N개이고, )는 정확히 N개이다. S는 지문에서 정의한 하나의 트리를 올바르게 나타낸다. 루트의 방문 종료 문자는 문자열의 마지막 문자이다. 자전거가 있는 대여소의 수는 0 이상 N 이하이다.

출력

정확히 N개의 줄을 출력한다. k+1번째 줄에는 안내 범위가 k일 때 연결 가능한 서로 다른 대여소 쌍의 수를 정수로 출력한다. 여기서 0 ≤ k ≤ N−1이다. 연결 가능한 쌍이 없으면 0을 출력한다.

3
BEE)))

0
1
3

4
EB)E)B))

0
3
6
6

1
E)

0

출처: Devin.KR 자체 제작