题目详情题解（0）讨论（0）提交记录（0）

CF504E.Misha and LCP on Tree

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

米沙有一棵树，树的每个顶点上都写有一个字符。他可以选择树上的两个顶点 ss 和 tt，并记录从 ss 到 tt 的路径上经过的所有顶点上的字符。我们将这样得到的字符串称为对应于二元组 (s,t)(s,t) 的字符串。

米沙有 mm 个询问，每个询问给出 44 个顶点 aa、bb、cc、dd；你需要找出对应于二元组 (a,b)(a,b) 和 (c,d)(c,d) 的字符串的最大公共前缀的长度。请你帮助他完成这个任务。

输入格式

第一行包含一个整数 nn（1≤n≤3000001 \leq n \leq 300000）——树中顶点的数量。

接下来一行包含 nn 个小写英文字母，第 ii 个字符表示第 ii 个顶点上的字符。

接下来 n−1n-1 行，每行包含一条边的信息，每条边由两个整数 uu、vv（1≤u,v≤n1 \leq u, v \leq n，u≠vu \neq v）组成，用空格隔开。

接下来一行包含一个整数 mm（1≤m≤10000001 \leq m \leq 1000000）——询问的数量。

接下来 mm 行，每行包含一个询问信息，由四个整数 aa、bb、cc、dd（1≤a,b,c,d≤n1 \leq a,b,c,d \leq 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

说明/提示

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页