ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5365: Misha and LCP on Tree

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：1 通过：1
提交提交记录统计Web Board

题目描述

Misha有一棵树，顶点上写有字符。他可以选择这棵树的两个顶点s和t，并写下位于从s到t的路径上的顶点的字符。

Misha有m个类型的查询：给你4个顶点a、b、c、d；您需要找到对应于对（a，b）和（c，d）的字符串的最大公共前缀。你的任务是帮助他。

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.
Input
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.
Output
For each query print the length of the largest common prefix on a separate line.
Examples
Input 
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
Output 
2
2
2
0
1
0

输入格式

第一行包含整数n（1≤n≤300000）−树中的顶点数。

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

接下来的n-1行包含关于边的信息。一条边由一对整数u，v（1≤u，v≤n，u≠v）定义，用空格隔开。

下一行包含整数m（1≤m≤1000000）−查询数。

接下来的m行包含有关查询的信息。查询由四个整数A、b、c、d（1≤A、b，c、d≤n）定义，用空格分隔。

输出格式

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

输入样例 复制 

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

输出样例 复制 

2
2
2
0
1
0

分类标签