You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

"怎么这么简单啊"

题目描述

具体地，给定一颗有$n$个结点的树，以及一个长度为$n$ 的仅包含小写字母的字符串$S$，树上的每一个结点$i$都代表一个字符$Si$

给出$q$次询问，每次给定两个整数$u$，$v$，询问：$u$，$v$之间的简单路径结点的字符能否经过重排构成一个回文串

数据范围

$1\leq n\leq 5e5$

$1\leq q \leq 5e5$

$1\leq u , v \leq n$

输入描述

第一行输入一个整数$n$，表示结点个数

下面$n-1$行，每行输入两个正整数$x$，$y$表示两点之间有一条边

第$n+1$行输入一个长度为$n$的字符串

第$n+2$行输入一个正整数$q$，表示询问次数

下面$q$行，每行输入两个正整数$u$，$v$表示询问的两个点

输出描述

输出$q$行，如果当前简单路径结点字符能通过重排构成回文串则输出$YES$

否则输出$NO$

示例

6
1 2
1 4
2 6
2 3
4 5
cbabaa
4
6 3
4 2
3 5
1 3

YES
YES
YES
NO