奇妙的脑回路
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述 

染火枫林，琼壶歌月，长歌倚楼。
岁岁年年，花前月下，一尊芳酒。
水落红莲，唯闻玉磬，但此情依旧。
给定一棵有 n 个结点的有根树，根结点编号为 1，每个结点都对应一个小写拉丁字母 a_{i} 作为它们的权值。
现在有 q 次操作，操作分为两种：
1. 给定结点编号 x , 将以 x 为根的子树中的所有结点(包括自己)的权值 a_{i} 全部 + 1。（a \rightarrow b , b \rightarrow c ,…… ，y \rightarrow z , z \rightarrow a）
2. 给定两个结点编号 x , y , 询问以 x,y 为端点的简单路径上有多少个结点可以作为树上任意一条长度不小于2的路径所构成的回文串的回文中心。
对于每次操作 2 ，输出一个整数表示答案。

输入描述:

第一行输入一个整数 n (1\leq n \leq 2\times10^{5}) 表示树上点个数。
接下来 n - 1 行，每行输入两个整数 u, v (1\leq u,v \leq n), 表示结点编号为 u , v 的两个点之间有一条边。
接下来一行输入 n 个小写字母 a_{i} 表示编号为 i 的结点对应的字母权值。
接下来一行输入一个整数 q (1\leq q \leq 2\times 10^5) 表示操作的次数。
下面 q 行，每行先输入一个整数 op (1\leq op \leq2) 表示对应的操作种类，
如果 op = 1 , 则紧跟着输入一个整数 x (1\leq x \leq n) 表示被修改子树的根结点。
如果 op = 2 , 则紧跟着输入两个以空格隔开的整数 x,y (1\leq x,y \leq n) 表示询问的简单路径的端点。

输出描述:

对于每次操作 2 ，输出一个整数表示答案。
示例1

输入

复制 
5
1 2
2 3
1 4
4 5
a b z b z
5
2 3 5
1 3
2 3 5
1 5
2 3 5

输出

复制 
1
2
3