Queries On Tree

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
You are given a tree of N nodes numbered from 1 to N.
The i^{th} edge connecting node u_{i} and v_{i} has a weight of w_{i}.
Your target is to handle the queries of the following two types:

"1 i c" : Update the weight of i^{th} edge with the new weight c.
(1 represents the query type).  "2 u v" : Find the length of the path from node u to v. (2 represents the query type).
Input
 The first line contains a single integer N.
 Each of the next N  1 lines contains three integers u v w, representing an edge
between u and v with the weight of w.  The next line contains a single integer Q representing the number of queries
 Each of the next Q lines contains three integers representing a query as described above.
Output
 For each query of type 2, output the answer in a single line.
Constraints
All test:
 1 ≤ i < N
 1 ≤ u, v ≤ N; u ≠ v
 1 ≤ w, c ≤ 10^{4}
40 points:
 1 ≤ N, Q ≤ 10^{3}
60 points:
 1 ≤ N, Q ≤ 10^{5}
Example
Input: 5 1 2 2 2 3 4 4 2 3 5 4 1 3 2 5 3 1 3 1 2 5 3 Output: 8 6
Explanation
The path from 5 to 3 is 5 > 4 > 2 > 3. Initially this path has the length of 1 + 3 + 4 = 8.
After the weight of the edge connect 4 and 2 was changed to 1, the new length of the path is 1 + 1 + 4 = 6.
Author:  tuananh93 
Tester:  stzgd 
Editorial  http://discuss.codechef.com/problems/TAQTREE 
Tags  dfsorder, hld, ltime19, medium, tuananh93 
Date Added:  6122014 
Time Limit:  2 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. 