Updating Edges on Trees

All submissions for this problem are available.
Read problems statements in English, Mandarin Chinese and Russian as well.
You have a tree consisting of N vertices numbered 1 to N.
Initially each edge has a value equal to zero. You have to first perform M1 operations and then answer M2 queries. Note you have to first perform all the operations and then answer all queries after all operations have been done.
Operations are defined by:
A B C D: On the path between nodes numbered A and B increase the value of each edge by 1, except for those edges which occur on the path between C and D. Note that there is an unique path between every pair of nodes ie. we don't consider values on edges for finding the path. All four values given in input will be distinct.
Queries are of the following type:
E F: Print the sum of values of all the edges on the path between two distinct nodes E and F. Again the path will be unique.
Input
Input description.
First line contains N, M1 and M2. Each of the next N1 lines contain two integers u v denoting an undirected edge between node numbered u and v. Each of the next M1 lines contain four integers A_{i} B_{i} C_{i} D_{i}, denoting the operations. Each of the next M2 lines contain two integers E_{i} F_{i} denoting the queries.
Output
For each query, print the required answer in one line.
Constraints
Example
Input: 5 2 2 1 2 2 4 2 5 1 3 1 4 2 3 3 4 2 5 4 5 4 3 Output: 2 4
Explanation
On first operation, value of edge (24) is increased by one. On second operation, value of edges (13), (12), (24) are increased by one.
Warning:Use fast input/output. Large input files.
Author:  darkshadows 
Editorial  http://discuss.codechef.com/problems/UPDTREE 
Tags  cook50, darkshadows, dfs, dynamicprogramming, lca, mediumhard 
Date Added:  15092014 
Time Limit:  3.5 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 
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. 