Period on tree

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given an undirected tree of N vertices, each of which edges is marked with some lowercase Latin letter between a and z.
It's easy to notice that, if you select some distinct vertices u and v and write down a sequence of characters on the shortest path from u to v, you will get a lowercase string corresponding to this path.
Let's call any string t a period of some string s if s can be obtained by concatenating the string t to itself one or more times.
Your task is to process, on a given tree, the following two types of queries:
 1 u v  output the length of the shortest period of the string corresponding to the path from u to v.
 2 u v c  replace the character marked on the edge between u and v with the character c.
Input
The first line of each test case contains a single integer T denoting the number of tests in input. The description of T test cases follows.
The first line of a test case contains an integer N — the number of vertices in the tree.
The next N  1 lines contains 2 spaceseparated entities: integer u_{i}, integer v_{i} and a character c_{i} denoting the edge between u_{i} and v_{i} marked with character c_{i} on it.
The next line contains one integer M denoting the number of queries.
Each of the next M lines contains three spaceseparated integers type_{i}, v_{i}, u_{i}.
If type_{i}=2, then character c_{i} follows these integers.
Output
For each query of type 1 you should output minimal period of string corresponding to this query.
Constraints
 1 ≤ T ≤ 10
 2 ≤ N, M ≤ 10^{5}
 u_{i} ≠ v_{i}, 1 ≤ v_{i}, u_{i},≤ N
 For each query of second type, it is guaranteed that u_{i} is adjacent to v_{i}
 Sum of N over all test cases in a single file will not be greater then 5*10^{5}
 Sum of M over all test cases in a single file will not be greater then 5*10^{5}
Subtasks
Subtask 1 (15 points): N, M ≤ 1*10^{4}, sum of N ≤ 5*10^{4}, sum of M ≤ 5*10^{4} in a single file.
Subtask 2 (25 points): N, M ≤ 5*10^{4}, sum of N ≤ 10^{5}, sum of M ≤ 10^{5} in a single file.
All the queries in this subtask have the first type
Subtask 3 (60 points): Original constraints
Example
Input: 2 3 1 2 a 1 3 b 4 1 1 2 1 2 3 2 1 3 a 1 2 3 4 1 2 a 2 3 b 3 4 a 3 1 1 4 2 2 3 a 1 1 4 Output: 1 2 1 3 1
Explanation
In first test case, period of strings "a", "aa" is "a", and period of "ab" is "ab".
In second test case, the only period of string "aba" is "aba" itself. Note that not "ab" is not a period, as "aba" is a prefix of "abab", but is not the same.
Since input file can be fairly large (about 15 MB), it's recommended to use fast I/O (for example, in C++, use scanf/printf instead of cin/cout).
Author:  tehnar 
Tester:  iscsi 
Editorial  http://discuss.codechef.com/problems/TREEP 
Tags  bit, decomposition, fenwick, hashing, lca, mediumhard, nov15, tehnar 
Date Added:  22092015 
Time Limit:  1  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions