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.
First line contains N, M1 and M2. Each of the next N-1 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 Ai Bi Ci Di, denoting the operations. Each of the next M2 lines contain two integers Ei Fi denoting the queries.
For each query, print the required answer in one line.
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
On first operation, value of edge (2-4) is increased by one. On second operation, value of edges (1-3), (1-2), (2-4) are increased by one.
Warning:Use fast input/output. Large input files.
|Tags||cook50, darkshadows, dfs, dynamic-programming, lca, medium-hard|
|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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.