Tree Sequences

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/AUG19/hindi/TSEQ.pdf), [Bengali](http://www.codechef.com/download/translated/AUG19/bengali/TSEQ.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/AUG19/mandarin/TSEQ.pdf), [Russian](http://www.codechef.com/download/translated/AUG19/russian/TSEQ.pdf), and [Vietnamese](http://www.codechef.com/download/translated/AUG19/vietnamese/TSEQ.pdf) as well. You are given a tree with $N$ vertices numbered $1$ through $N$. For each valid $i$, initially, vertex $i$ has value $W_i$. The value of each vertex can be either $1$ or a nonnegative integer. At any time, let's denote the sequence of values of vertices on the path from vertex $u$ to vertex $v$ by $S(u, v)$. We are interested in replacing each element $1$ in such a sequence by a nonnegative integer (not necessarily the same for each $1$). You should process $Q$ queries of five types:  `UPDATE U X`: Change the value of vertex $U$ to $X$.  `INCREASING U V A B`: Find the number of ways to replace each $1$ in the sequence $S(U, V)$ by an integer such that the resulting sequence is **strictly increasing** and contains only integers between $A$ and $B$ (inclusive).  `DECREASING U V A B`: Find the number of ways to replace each $1$ in the sequence $S(U, V)$by an integer such that the resulting sequence is **strictly decreasing** and contains only integers between $A$ and $B$ (inclusive).  `NONDECREASING U V A B`: Find the number of ways to replace each $1$ in the sequence $S(U, V)$ by an integer such that the resulting sequence is **nondecreasing** and contains only integers between $A$ and $B$ (inclusive).  `NONINCREASING U V A B`: Find the number of ways to replace each $1$ in the sequence $S(U, V)$ by an integer such that the resulting sequence is **nonincreasing** and contains only integers between $A$ and $B$ (inclusive). ### Input  The first line of the input contains two spaceseparated integers $N$ and $Q$.  The second line contains $N$ spaceseparated integers $W_1, W_2, \ldots, W_N$.  Each of the next $N1$ lines contains two spaceseparated integers $U$ and $V$ denoting that vertices $U$ and $V$ are connected by an edge.  $Q$ lines follow. Each of these lines describes one query in the format given above. ### Output For each query except the `UPDATE` queries, print a single line containing one integer ― the number of ways to replace each $1$, modulo $10^9 + 7$. ### Constraints  $1 \le N, Q \le 10^5$  $1 \le U, V \le N$  $1 \le W_i \le 10^6$ for each valid $i$  $0 \le A \le B \le 10^6$  $1 \le X \le 10^6$ ### Subtasks **Subtask #1 (10 points):** $1 \le N, Q \le 1,000$ **Subtask #2 (10 points):**  $W_i = 1$ for each valid $i$  $X = 1$ **Subtask #3 (80 points):** original constraints ### Example Input ``` 8 3 1 2 3 1 1 1 1 1 1 2 2 3 2 5 2 6 4 5 5 7 5 8 INCREASING 1 5 1 10 UPDATE 1 1 NONDECREASING 1 5 0 10 ``` ### Example Output ``` 8 27 ```Author:  daniel_1999 
Editorial  https://discuss.codechef.com/problems/TSEQ 
Tags  aug19, combinatorics, daniel_1999, hard, hld, segmenttree, vijju123 
Date Added:  1052019 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions