Roots of a Tree
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
You are given a tree with N nodes, numbered from 1 to N. You need to handle the queiries of the following two types:
- + x y. Add a path going from the node x to the node y (or from y to x because it's actually irrelevant). We will never add the path that is already a present one.
- - x y. Delete the path going from the node x to the node y. It is guaranteed that such path exists and after its last adding it haven't yet been deleted.
If we root the tree at the node t and for every present (added and not yet deleted) path, the least common ancestor of its endpoints is also one of the endpoints of this path, then we call the node t a possible root.
We ask you to output the product of all the possible roots' indexes after every query.
The first line of input contains two single space separated integers N and M - the number of nodes in the tree and the number of queries respectively.
The following N-1 lines contain pairs of integers denoting the edges of a tree. The pair X Y corresponds to the edge between the nodes X and Y.
Then there are M lines denoting the queries in the form described above.
Output M lines. Output the product of all the possible roots' numbers modulo 109+7 after the performing of the i-th query on the i-th line. If there are no possible roots, output -1 on this line instead.
- 1 ≤ X, Y ≤ N
- 1 ≤ x, y ≤ N
- 1 ≤ N, M ≤ 100 - 42 points.
- 1 ≤ N, M ≤ 105 - 58 points.
Input: 5 4 1 2 2 3 3 4 4 5 + 1 3 + 3 5 - 1 3 - 3 5 Output: 60 15 30 120
|Tags||dfs, easy-medium, ltime12, segment-tree, xcwgf666|
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.