시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 1832 | 278 | 199 | 17.720% |
Baekjoon Online Judge를 비롯한 여러 온라인 채점 사이트에서는 각 유저를 고유한 ID로 구분한다. 이 ID는 핸들(Handle)이라고도 하며, 보통 여러 온라인 채점 사이트에서 동일하거나 비슷한 ID를 사용한다. 이러한 이유로 여러 사이트에서 활동하는 알고리즘 랭커들은 본명보다 핸들이 더 잘 알려지고는 한다.
알고리즘 최정상을 꿈꾸는 효규는 깊은 고민에 빠져있다. 바로 핸들을 정하는 일이다. 적당히 멋있으면서도 의미 있는 핸들을 원하지만, 도저히 떠오르지 않는다. 그 모습을 지켜보던 상원이는 주머니에 있던 트리 하나를 효규에게 주며 핸들 정하는 방법을 제안했다.
이렇게 얻어지는 문자열을 효규의 핸들로 정한다. 하지만 얻을 수 있는 문자열의 종류가 너무 많기 때문에 그 중 사전상 가장 마지막에 오는 문자열을 핸들로 정하기로 했다. 상원이가 효규에게 준 트리의 정보가 주어졌을 때, 효규가 정할 핸들이 무엇인지 알아보자.
첫 번째 줄에 $N$이 주어진다. $(1 \le N \le 500\,000)$
두 번째 줄에 각 정점에 적혀 있는 알파벳 소문자가 공백 없이 순서대로 주어진다.
세 번째 줄부터 $N-1$개의 줄에 두 정수 $u$, $v$가 공백으로 구분되어 주어진다. $u$번 정점과 $v$번 정점 사이 간선을 나타낸다. $(1 \le u, v \le N, u \neq v)$
효규가 정할 핸들을 출력한다.
8 dfcjsasb 8 4 6 3 1 3 2 1 4 1 4 7 2 5
djs
효규가 얻을 수 있는 문자열은 사전순으로 "$\text{dfs}$", "$\text{dca}$", "$\text{djb}$", "$\text{djs}$"이므로 "$\text{djs}$"를 핸들로 정한다.
7 aaaaaaa 1 2 1 3 3 4 3 5 5 6 5 7
aaaa
효규가 얻을 수 있는 문자열은 사전순으로 "$\text{aa}$", "$\text{aaa}$", "$\text{aaaa}$", "$\text{aaaa}$"이므로 "$\text{aaaa}$"를 핸들로 정한다.