시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB197675.000%

문제

흑곰과 흰곰은 룬 숲에 사는 커모드 곰 남매이다. 두 곰은 숲에 있는 나무 한 그루에서 문자열 놀이를 하려고 한다. 룬 숲의 나무는 $1$부터 $N$까지의 정점과 $N-1$개의 양방향 간선으로 이루어진 연결 그래프이다. 나무의 $i$번 정점에는 알파벳 대문자 $r_i$가 적혀있다. 두 곰은 다음과 같은 규칙을 통해 나무에서 각자 원하는 문자열을 하나씩 만든다.

  1. 빈 문자열 $S$가 존재한다.
  2. 나무에서 정점 $x$와 정점 $y$를 선택한다. 두 정점은 같아도 된다.
  3. 정점 $x$에서 시작해서 정점 $y$에서 끝나는 단순 경로(중복된 정점이 존재하지 않는 경로)를 따라 이동하며 방문한 순서대로 정점에 적힌 문자를 $S$의 오른쪽 끝에 붙인다. 정점 $x$와 정점 $y$에 적힌 문자도 포함한다.

이러한 규칙을 통해 나무에서 만든 문자열을 $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)$를 왼쪽 끝부터 비교했을 때 겹치는 글자의 개수를 출력한다.

예제 입력 1

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

예제 출력 1

0
2
3
0
4

출처

Contest > SW마에스트로 > 제13기 알고리즘 대회 G번