풀레코와 개미

면접 대비

시간 제한1초메모리 제한64 MB

요약

U와 D로 기록된 트리 순회 기록에서 주어진 두 분기점 A와 B 사이의 트리 거리를 출력합니다.

문제

나무 둘레를 따라 가는 개미 경로를 U(위로 분기)와 D(아래로 분기) 문자열로 표현한다. 문자열 인덱스 $k$ 는 루트에서 가지를 따라 $k$ 번 걸은 뒤 있는 분기점이다.

개미의 시작 인덱스 $A$ 와 안전하다고 생각하는 인덱스 $B$ 가 주어질 때, 두 분기점 사이 나무 거리(가지 수)를 출력한다.

첫 줄 $A$ , $B$ (0-based 인덱스). 다음 줄 UD 문자열 $S$ .

두 분기점 사이 거리 한 정수.

$|S| < 10^6$ , $S$ 는 유효한 나무를 나타낸다.