Dynamic GCD

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 i^{th} vertex being v_{i}. 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).
Input
First line of input contains an integer N denoting the size of the vertex set of the tree. Then follow N  1 lines, i^{th} of which contains two integers a_{i} and b_{i} denoting an edge between vertices a_{i} and b_{i} in the tree. After this follow N space separated integers in a single line denoting initial values v_{i} 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 0based.
Output
For every find query, print the answer to that query in one line by itself.
Example
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
Constraints
1 <= N <= 50000
1 <= Q <= 50000
0 <= u, v <= N1
1 <= v_{i} <= 10^4
0 <= d <= 10^4
Author:  yellow_agony 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/DGCD 
Tags  hard, heavylight, july12, numbertheory, yellow_agony 
Date Added:  4122011 
Time Limit:  0.21066 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, 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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 