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.
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 space-separated entities: integer ui, integer vi and a character ci denoting the edge between ui and vi marked with character ci on it. The next line contains one integer M denoting the number of queries. Each of the next M lines contains three space-separated integers typei, vi, ui. If typei=2, then character ci follows these integers.
For each query of type 1 you should output minimal period of string corresponding to this query.
- 1 ≤ T ≤ 10
- 2 ≤ N, M ≤ 105
- ui ≠ vi, 1 ≤ vi, ui,≤ N
- For each query of second type, it is guaranteed that ui is adjacent to vi
- Sum of N over all test cases in a single file will not be greater then 5*105
- Sum of M over all test cases in a single file will not be greater then 5*105
SubtasksSubtask 1 (15 points): N, M ≤ 1*104, sum of N ≤ 5*104, sum of M ≤ 5*104 in a single file. Subtask 2 (25 points): N, M ≤ 5*104, sum of N ≤ 105, sum of M ≤ 105 in a single file. All the queries in this subtask have the first type Subtask 3 (60 points): Original constraints
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
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).
|Tags||bit, decomposition, fenwick, hashing, lca, medium-hard, nov15, tehnar|
|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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.