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