Misha and LCP on Tree

题意翻译

- 给定一棵 $n$ 个节点的树，每个节点有一个小写字母。 - 有 $m$ 组询问，每组询问为树上 $a \to b$ 和 $c \to d$ 组成的字符串的最长公共前缀。 - $n \le 3 \times 10^5$，$m \le 10^6$。

题目描述

Misha has a tree with characters written on the vertices. He can choose two vertices $s$ and $t$ of this tree and write down characters of vertices lying on a path from $s$ to $t$ . We'll say that such string corresponds to pair $(s,t)$ . Misha has $m$ queries of type: you are given $4$ vertices $a$ , $b$ , $c$ , $d$ ; you need to find the largest common prefix of the strings that correspond to pairs $(a,b)$ and $(c,d)$ . Your task is to help him.

输入输出格式

输入格式

The first line contains integer $n$ ( $1<=n<=300000$ ) — the number of vertices in the tree. Next follows a line consisting of $n$ small English letters. The $i$ -th character of the string corresponds to the character written on the $i$ -th vertex. Next $n-1$ lines contain information about edges. An edge is defined by a pair of integers $u$ , $v$ ( $1<=u,v<=n$ , $u≠v$ ), separated by spaces. The next line contains integer $m$ ( $1<=m<=1000000$ ) — the number of queries. Next $m$ lines contain information about queries. A query is defined by four integers $a$ , $b$ , $c$ , $d$ ( $1<=a,b,c,d<=n$ ), separated by spaces.

输出格式

For each query print the length of the largest common prefix on a separate line.

输入输出样例

输入样例 #1

6
bbbabb
2 1
3 2
4 3
5 2
6 5
6
2 5 3 1
1 5 2 3
5 6 5 6
6 3 4 1
6 2 3 4
2 2 4 5


输出样例 #1

2
2
2
0
1
0