All submissions for this problem are available.
You're given a tree on N vertices. Each vertex has a positive integer written on it, number on the ith vertex being vi. Your program must process two types of queries :
1. Find query represented by F u v : Find out gcd of all numbers on the unique path between vertices u and v in the tree (both inclusive).
2. Change query represented by C u v d : Add d to the number written on all vertices along the unique path between vertices u and v in the tree (both inclusive).
First line of input contains an integer N denoting the size of the vertex set of the tree. Then follow N - 1 lines, ith of which contains two integers ai and bi denoting an edge between vertices ai and bi in the tree. After this follow N space separated integers in a single line denoting initial values vi at each of these nodes. Then follows a single integer Q on a line by itself, denoting the number of queries to follow. Then follow Q queries, each one on a line by itself. Each query is either a find query or a change query with format as given in problem statement. Note that all vertices are 0-based.
For every find query, print the answer to that query in one line by itself.
Input: 6 0 4 0 5 1 5 5 2 3 5 3 1 3 2 4 2 5 F 3 5 C 1 3 1 C 3 4 4 F 3 0 F 2 5 Output: 2 7 1
1 <= N <= 50000
1 <= Q <= 50000
0 <= u, v <= N-1
1 <= vi <= 10^4
0 <= d <= 10^4
|Tags||hard, heavy-light, july12, number-theory, yellow_agony|
|Time Limit:||0.21066 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.