시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 19 | 7 | 6 | 75.000% |
흑곰과 흰곰은 룬 숲에 사는 커모드 곰 남매이다. 두 곰은 숲에 있는 나무 한 그루에서 문자열 놀이를 하려고 한다. 룬 숲의 나무는 $1$부터 $N$까지의 정점과 $N-1$개의 양방향 간선으로 이루어진 연결 그래프이다. 나무의 $i$번 정점에는 알파벳 대문자 $r_i$가 적혀있다. 두 곰은 다음과 같은 규칙을 통해 나무에서 각자 원하는 문자열을 하나씩 만든다.
이러한 규칙을 통해 나무에서 만든 문자열을 $S\left( x,y \right)$라고 부른다. 문자열 놀이를 하는 동안 나무에 적혀있는 문자가 사라지거나 변하는 일은 없다.
흑곰은 정점 $a$와 정점 $b$를 골라 문자열 $S\left( a,b \right)$를 만든다. 흰곰은 정점 $c$와 정점 $d$를 골라 문자열 $S\left( c,d \right)$를 만든다. 그리고 두 문자열을 왼쪽 끝부터 비교했을 때 몇 글자가 겹치는지 확인한다. 이것이 바로 커모드 곰의 문자열 놀이이다.
룬 숲의 나무 한 그루가 주어진다. 두 곰은 이 나무에서 문자열 놀이를 $M$번 할 것이다. $i$번째 놀이에서 흑곰이 고른 정점 $a_i,b_i$와 흰곰이 고른 정점 $c_i,d_i$가 주어진다. 이때 $S\left( a_i,b_i \right)$와 $S\left( c_i,d_i \right)$를 왼쪽 끝부터 비교했을 때 몇 글자가 겹치는지 답해야 한다.
첫 번째 줄에 정점의 개수 $N$이 주어진다. $(2\leq N\leq 2\times 10^5)$
두 번째 줄부터 $N$개의 줄에 걸쳐 $i+1$ 번째 줄에 $i$번 정점에 써있는 문자 $r_i$가 주어진다. $r_i$는 알파벳 대문자이다.
$N+2$ 번째 줄부터 $N-1$개의 줄에 걸쳐 간선의 양 끝 정점 $u_i$와 $v_i$가 공백으로 구분되어 주어진다. $(1\leq u_i\lt v_i\leq N)$
$2N+1$ 번째 줄에 정수 $M$이 주어진다. $(1\leq M\leq 2\times 10^5)$
$2N+2$ 번째 줄부터 $M$개의 줄에 걸쳐 흑곰과 흰곰이 고른 정점 $a_i,b_i,c_i,d_i$가 공백으로 구분되어 주어진다. $(1\leq a_i,b_i,c_i,d_i\leq N)$
첫 번째 줄부터 $M$개의 줄에 걸쳐 $S\left( a_i,b_i \right)$와 $S\left( c_i,d_i \right)$를 왼쪽 끝부터 비교했을 때 겹치는 글자의 개수를 출력한다.
5 B B A C C 1 2 2 3 2 4 1 5 5 3 5 1 1 1 2 2 5 4 1 5 3 5 3 3 5 4 5 5 4
0 2 3 0 4
Contest > SW마에스트로 > 제13기 알고리즘 대회 G번