CF504E Misha and LCP on Tree

米沙有一棵树，树的每个顶点上都写有一个字符。他可以选择树上的两个顶点 $s$ 和 $t$，并记录从 $s$ 到 $t$ 的路径上经过的所有顶点上的字符。我们将这样得到的字符串称为对应于二元组 $(s,t)$ 的字符串。 米沙有 $m$ 个询问，每个询问给出 $4$ 个顶点 $a$、$b$、$c$、$d$；你需要找出对应于二元组 $(a,b)$ 和 $(c,d)$ 的字符串的最大公共前缀的长度。请你帮助他完成这个任务。

第一行包含一个整数 $n$（$1 \leq n \leq 300000$）——树中顶点的数量。 接下来一行包含 $n$ 个小写英文字母，第 $i$ 个字符表示第 $i$ 个顶点上的字符。 接下来 $n-1$ 行，每行包含一条边的信息，每条边由两个整数 $u$、$v$（$1 \leq u, v \leq n$，$u \neq v$）组成，用空格隔开。 接下来一行包含一个整数 $m$（$1 \leq m \leq 1000000$）——询问的数量。 接下来 $m$ 行，每行包含一个询问信息，由四个整数 $a$、$b$、$c$、$d$（$1 \leq a,b,c,d \leq n$），用空格隔开。

对于每个询问，输出一个整数，表示最大公共前缀的长度，各占一行。

由 ChatGPT 5 翻译