← 返回题目列表

Codeforces · 504/E

E. Misha 和 LCP 在树上

中文机器翻译题面 查看原题

Misha有一棵树,树的顶点上写着字符。他可以选择这棵树的两个顶点 s 和 t,并写下从 s 到 t 的路径上的顶点的字符。我们会说这样的字符串对应于 (s, t) 对。

Misha 有 m 个类型的查询:给定 4 个顶点 a、b、c、d;您需要找到与 (a, b) 和 (c, d) 对相对应的字符串的最大公共前缀。你的任务是帮助他。

输入

第一行包含整数 n (1 ≤ n ≤ 300 000) — 树中的顶点数。

接下来是由 n 个小英文字母组成的行。字符串的第 i 个字符对应于第 i 个顶点上写入的字符。

接下来的 n - 1 行包含有关边缘的信息。一条边由一对整数 u、v (1 ≤ u, v ≤ n, u ≠ v) 定义,并用空格分隔。

下一行包含整数 m (1 ≤ m ≤ 1 000 000) — 查询数。

接下来的 m 行包含有关查询的信息。查询由四个整数 a、b、c、d (1 ≤ a、b、c、d ≤ n) 定义,并用空格分隔。

输出

对于每个查询,在单独的行上打印最大公共前缀的长度。

示例

输入 #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