Chef and Tree

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has a tree on N nodes. Each node v has an integer label C_{v} attached to it. Chef also has two other integers, A and B. He needs to run Q queries on the tree, each of which can be one of the following two types:
Please help Chef run these queries.
Input
The first line of input contains an integer T denoting the number of test cases.Output
For each query of the second type, output a single line containing a single integer — its result.Constraints
 1 ≤ T ≤ 10^{5}
 1 ≤ N, Q ≤ 10^{5}
 1 ≤ u, v ≤ N
 0 ≤ A, B, C_{i} ≤ 10^{9}
 1 ≤ w ≤ 10^{4}
 Sum of N over all test cases cannot be greater than 10^{5}.
 Sum of Q over all test cases cannot be greater than 10^{5}.
 All numbers in the input are integers.
Example
Input: 1 5 6 1 0 1 2 3 4 5 1 2 1 3 2 4 2 5 1 4 3 1 2 4 3 1 3 3 1 2 3 3 1 3 3 2 2 4 3 Output: 3 0 4
Author:  mgch 
Editorial  http://discuss.codechef.com/problems/CHEFTREE 
Tags  cook65, datastructure, hard, heavylight, mgch, segmenttree 
Date Added:  9122015 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5 
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. 