PROBLEM LINK:
Setter- Данило Мочернюк
Tester- Suchan Park
Editorialist- Abhishek Pandey
DIFFICULTY:
HARD
PRE-REQUISITES:
Heavy Light Decomposition, Segment Tree (It is expected that you know range product query on a segment tree), Basic Combinatorics , LCA
PROBLEM:
Given a tree of N nodes (with each node having some value W_i), answer following queries-
- Update the value of some node to X
- Replace -1's in shortest path from u to v such that -
- Starting from u to v, the series has the required relative order (i.e. strictly increasing, non-decreasing, strictly decreasing, non-increasing)
- All numbers in path from u to v lie in range [A,B]
QUICK-EXPLANATION:
Key to AC- Realize that number of ways by which you can replace -1's is bounded by the non-negative W_i's (if existing) on both extremes of the path.
Realize that if we want the path from u to v to be strictly increasing, then this means that path from v to u should be strictly decreasing as well. Similar argument holds good for case of non-increasing and non-decreasing as well. Hence, its worthwhile to look at implementations where we can exploit this reusability. The easiest method would be to change path from u to v to preferably v to u (i.e. reverse the path) and reuse the same logic we did to answer for increasing/strictly-increasing part of the question.
Lets for now talk about the increasing query, as we can answer the decreasing queries by reusing the logic for increasing queries.
Let me call some value W_i as bounding value(s) if its not equal to -1, and if there is a group of zero or more -1 between it uptil next non-negative W_i if we follow a given direction. Now, notice that on a given path, the number of ways to replace -1 such that the sequence is increasing/strictly increasing depends on these bounding values. This is because no matter how large the values of A and B are, any value in middle of the path (and bounded by the bounding values) must lie between these 2 for the increasing/strictly increasing condition to hold good. We will use this in our implementation.
Use HLD to decompose the tree into chains, and make 4 segment trees as-
- One to answer the strictly increasing query if we go up from some node, say node u.
- One to answer the strictly increasing query if we go down from some node, say node u.
- One to answer the increasing query if we go up from some node, say node u.
- One to answer the increasing query if we go down from some node, say node u.
The directions are important so that we can reuse the same logic to answer the decreasing/strictly-decreasing queries by reversing the path.
We can store the results for each “group” of -1's in the segment tree (along with other data to keep the answer consistent, or obtain required intermediate values) and do a range product to answer each query in O(log^2 N). Note that for the trailing and starting -1's you mught have to handle manually for easier implementation.
EXPLANATION:
The editorial will chiefly focus on the idea part. The implementation part of it, like any other HLD question, is a bit tedious - and the best way to learn it is to actually struggle through it and learn from other people’s elegant solution. The best I can do is to give an idea on how the HLD is working, but the implementation is something one needs to do for himself.
I have divided the editorial into the following sections-
- How to reuse the logic for increasing queries to answer for decreasing queries.
- Significance of bounding values
- Combinatorics Involved
- Some notes on implementation
The answers of all “(Why?)” are in bonus section.
Regarding Queries
The first thing which makes a coder’s eyeballs bulge on seeing the problem is that we have to answer 5 queries!! And each of them seem equally tedious.
And honestly, if one does not think and straight away goes head on to tackle the question just like that, then it will be an implementation nightmare for him. So lets see how to avoid it 
Look at the strictly increasing query. It says that we need to replace each -1 in path from vertex u to vertex v such that all integers in this path are between [A,B] and that the path is strictly increasing. Now, if the path from u to v is strictly increasing, this will also mean that the path from v to u must be strictly decreasing as well.
A similar argument holds good for the non-increasing and non-decreasing queries. That is, if the path from u to v is non-increasing, then the reverse path from v to u is non-decreasing!
This means that, if we can somehow account for the path and/or direction (which helps in accounting for path!), then there is a non-trivial chance to reuse the implementation for increasing and non-decreasing queries to answer the decreasing and non-increasing queries. How we achieve so, is an implementation aspect which we will integrate in the last section.
Significance of Bounding Values
For sake of clarity, lets consider the path from i to j having values W as following - [W_i, -1,-1,-1,...,-1,W_j], where W_i and W_j are not equal to -1. Notice that no matter what A and B limits are given by the query, the number of ways to fill -1 with some value such that the path is, say, strictly increasing, are fixed and dependent on values of W_i and W_j.
In other words, the number of ways depend on W_i and W_j and not on A and B for such cases, where all -1's are bounded by some non negative values of W_i and W_j . This is because none of the -1 in the range can be less than W_i or greater than W_j. (Obviously, if W_i > W_j holds then the answer for our case of strictly increasing is 0 anyway). This means that the “true” bound for the group of -1's in between W_i to W_j is actually [W_i,W_j] and not [A,B].
Now, look at our path in the query from Node u to Node v. Now, see that you can look at the path as follows-
- There MAY be some -1's in the beginning.
- There MAY be some -1's at the end.
- If number of W_i>-1 on the path is 0 or just 1, then above 2 cases cover it all.
- If number of W_i>-1 is 2 or more, you will see that the path can be divided into “chunks” which I took an example of. That is, some non-negative W_i, then zero or more occurrences of -1 and then the next bounding value W_j. For those, the answer does not depend on A and B.
For cases pointed to by point 1 and 2, we can easily answer manually knowing the value of A, B and the number of occurrences of -1 which we have to fill. For the case pointed at by point 3, realize that since the answer depends on bounding W_i and W_j, we can pre-compute this at the beginning, and can update the results while handling updates. The important thing to note is, that we can avoid having to calculate this thing for all chunks again and again while answering the other 4 queries.
Now, we have O(N) such chunks (Why?). However, doing range product and updating some node naively (eg- using arrays) will be O(N) per query. Hence, we use a data structure like Segment Tree to do range product and updates in O(logN)
But how to calculate this number of ways? We will deal it in the Combinatorics section.
Combinatorics Involved
This section will deal with "How to select integers such that all numbers in the chunk are in range [W_i,W_j]
Lets say that the bounding values of our “chunk” is W_i and W_j. As we already saw that the solution to strictly decreasing and non-increasing queries can be calculated by reusing logic of increasing and non-decreasing, we will only discuss cases of increasing and non-decreasing.
For the 2 cases below, assume that for our “chunk” starting from node i to node j, our bounding values are W_i, W_j respectively. Also, assume that there are cnt occurrences of -1's to fill in the chunk.
- Increasing - This reduces to finding number of distinct elements in range (W_i,W_j) (Why?). Since both W_i and W_j are excluded, we have W_j-W_i-1 options, and have to pick cnt out of those. Hence the answer is {W_j-W_i-1} \choose cnt
- Non-Decreasing - What is the difference between above case and this one? In above case, repetitions were not allowed as it’d mean the sequence is not strictly increasing. However, in this case we can use repetitions. This reduces it to select integers in range [W_i,W_j] with repetitions, which as proved here to W_j-W_i+cnt \choose cnt
This deals with handling the chunks. But if you recall how we defined our path earlier, you’d recall that there is one more thing to touch. What about the -1's before our first chunk, or -1's after our last chunk, or what if there are no chunks at all!
- If there are no chunks, then it we have to fill all -1 with values in range [A,B]. Say there are cnt such values. You can easily find their formulas by substituting W_i=A and W_j=B in above formulas for non-decreasing query, and W_i=A-1 and W_j=B+1 for increasing query (as our formula for increasing excludes the end points!)
- Handing -1's before first chunk - Let the first chunk start with value K. Now, our problem reduces to filling all -1's with values in range [A,K]. Substitute W_i=A and W_j=K in above formulas for non decreasing query. For increasing query, W_i=A-1 and W_j=K (as we exclude both endpoints.)
- Handing -1 after the last chunk - Here, say the ending value of last chunk was K. Substitute W_i=K and W_j=B for non decreasing query, W_i=K and W_j=B+1 for the increasing query and find the answer
.
This handles the combinatorics aspect of the problem! The next section highlights some implementation aspects, mainly taken from setter’s solution.
Updates and Implementation Aspects
Lets first discuss the implementation aspects of the problem.
The very first thing is to use HLD to decompose our tree into chains, over which we can build a segment tree to answer range queries and handle updates. The implementation for HLD can in itself be lengthy, but it is something which cannot be helped 
.
The next task is to make segment tree over chains.
Notice that in our very first section, where we proved that the logic for increasing/non-decreasing queries can be used to answer the decreasing/non-increasing queries, we saw that direction mattered.
Like, having the sequence increasing in path from u to v meant having the sequence from path v to u to be decreasing. Or, allow me to state it like this-
“Having the sequence increasing from u to v is same as having the sequence increasing from u UP till LCA(u,v), and then having it increasing from LCA(u,v) DOWN to v”.
Similarly, the reverse of this path can be defined as-
“Path UP from v to LCA(u,v) and then from LCA(u,v) DOWN to u”.
Now, the direction where we are moving matters as it affects the boundary values of “chunks”. Eg- going from i to j, if we encounter a chunk [W_i,W_j] then going from j to i we will encounter the chunk [W_j,W_i]. Both of them will lead to different answers according to our combinatorics formula.
This means, that we should make one segment tree per direction for each type of query over a path/chain. Since we only need to implement for increasing and non-decreasing queries, the total number of segment trees we need is 2(directions)*2(queries)=4. As summarized in quick explanation, they will be as follows-
- One to answer the strictly increasing query if we go up from some node, say node u.
- One to answer the strictly increasing query if we go down from some node, say node u.
- One to answer the increasing query if we go up from some node, say node u.
- One to answer the increasing query if we go down from some node, say node u.
Now, while making the segment tree, make sure you store sufficient parameters to help you answer the queries across various chains. Storing just the range product can be insufficient (Why?), although it really depends on your implementation.
Updates are pretty simple to think of. The thing to note is that you need to update it on all 4 segment trees we defined above (if your implementation is similar to the one discussed). The updates are point updates, which honestly do not leave a lot of things to be discussed. If the endpoints of a chunk are updated then its easy as only the contribution of the chunk is to be recalculated. Howver, be careful of updates where a -1 is updated to some non-negative value, or if some existing value becomes -1, as then new chunks may be formed.
Aside from that, the best thing to tackle implementation can only be to see what elegant tricks others have applied. The idea for the problem is very neat, however it demands command over implementation to give full score
SOLUTION
Setter
#include <bits/stdc++.h>
#define LL long long
#define PB push_back
#define SZ(a) (int)(a.size())
using namespace std;
//WARNING!!!
const int MAX = 100005;
const int MAXFACT = 2000005;
//#warning
const int mod = 1000 * 1000 * 1000 + 7;
//0 - Non-decreasing
//1 - Increasing
int t , n , q;
int sz[MAX], in[MAX], out[MAX], rin[MAX] , val[MAX] , fact[MAXFACT] , inv[MAXFACT] , p[MAX] , nxt[MAX] , depth[MAX];
set<int> s[MAX];
int T[4][4 * MAX];
vector<vector<int> > g(MAX);
vector<vector<int> > g2(MAX);
int add(int a , int b)
{
return a + b >= mod ? a + b - mod : a + b;
}
int mult(int a , int b)
{
return a * (LL)b % mod;
}
bool isIn(int u , int v)
{
return in[u] >= in[v] && out[u] <= out[v];
}
int c(int N , int K)
{
if(N < K || N < 0 || K < 0)
return 0;
return mult(fact[N] , mult(inv[K] , inv[N - K]));
}
int modPow(int a , int step)
{
int ans = 1;
while(step)
{
if(step & 1)
ans = mult(ans , a);
step >>= 1;
a = mult(a , a);
}
return ans;
}
void init()
{
inv[0] = fact[0] = 1;
for(int i = 1; i < MAXFACT; i++)
{
fact[i] = mult(i , fact[i - 1]);
inv[i] = modPow(fact[i] , mod - 2);
}
}
int f(int type , int last , int v , int cnt)
{
if(last == -1)
return 1;
if(last > v)
return 0;
return type == 0 ? c(v - last + cnt , cnt) : c(v - last - 1, cnt);
}
void dfs_sz(int v = 0 , int P = -1)
{
sz[v] = 1;
for(auto &u: g[v])
{
if(u == P)
continue;
depth[u] = depth[v] + 1;
p[u] = v;
dfs_sz(u , v);
sz[v] += sz[u];
if(sz[u] > sz[g[v][0]])
swap(u, g[v][0]);
}
}
void dfs_hld(int v = 0 , int P = -1)
{
in[v] = t++;
if(val[v] != -1)
{
//cout << "Chotki:" << nxt[v] << endl;
s[nxt[v]].insert(in[v]);
}
rin[in[v]] = v;
for(auto u: g[v])
{
if(u == P)
continue;
nxt[u] = (u == g[v][0] ? nxt[v] : u);
dfs_hld(u , v);
}
out[v] = t;
}
void upd(int idx , int v , int tl , int tr, int pos , int value)
{
if(tl == tr)
{
T[idx][v] = value;
return;
}
int tm = (tl + tr) / 2;
if(pos <= tm)
upd(idx , v * 2, tl , tm , pos , value);
else
upd(idx , v * 2 + 1 , tm + 1 , tr , pos , value);
T[idx][v] = mult(T[idx][v * 2] , T[idx][v * 2 + 1]);
}
int get(int idx , int v , int tl , int tr , int l , int r)
{
if(l > r)
return 1;
if(tl == l && tr == r)
return T[idx][v];
int tm = (tl + tr) / 2;
return mult(get(idx , v * 2 , tl , tm , l , min(r , tm)) , get(idx , v * 2 + 1 , tm + 1 , tr , max(l , tm + 1) , r));
}
int get(int idx , int l , int r)
{
return get(idx , 1 , 0 , n - 1 , l , r);
}
void upd(int idx , int pos, int value)
{
upd(idx , 1 , 0 , n - 1 , pos , value);
}
void update(int u , int v , int i)//Next - cur
{
if(in[u] < in[v])
swap(u , v);
int dist = abs(in[u] - in[v]) - 1;
upd(0 , in[u] , f(0 , val[u] , val[v] , dist));
upd(1 , in[u] , f(1 , val[u] , val[v] , dist));
upd(2 , in[v] , f(0 , val[v] , val[u] , dist));
upd(3 , in[v] , f(1 , val[v] , val[u] , dist));
}
//0 - ND - Down
//1 - I - Down
//2 - ND - Up
//3 - I - Up
void del01(int idx)
{
for(int i = 0; i < 2; i++)
upd(i , idx , 1);
}
void del23(int idx)
{
for(int i = 2; i < 4; i++)
upd(i , idx , 1);
}
void del(int idx)
{
del01(idx);
del23(idx);
}
void push_up(int &ans , int &u , int &v , int &curSize1 , int &start , string type , int zsuv = 0 , bool debug = false)
{
//debug = 0;
//cerr << debug << endl;
auto it1 = s[nxt[u]].upper_bound(in[u]);
if(it1 == s[nxt[u]].begin())//Empty range
{
curSize1 += in[u] - in[v] + 1;
u = v;
u = p[u];
return;
}
it1--;
auto it2 = s[nxt[u]].lower_bound(in[v]);
//Valid *it2 <= *it1
if(it2 == s[nxt[u]].end() || *it2 > *it1)//Empty range
{
curSize1 += in[u] - in[v] + 1;
u = v;
u = p[u];
return;
}
if(zsuv == 0)
{
if(debug)
cerr << *it2 + 1 << " " << *it1 << endl;
ans = mult(ans , get(zsuv + (type == "I") , *it2 + 1, *it1));
}
else
ans = mult(ans , get(zsuv + (type == "I") , *it2, *it1 - 1));
//cerr << "Ans:" << ans << endl;
curSize1 += in[u] - *it1;
if(zsuv == 0)
ans = mult(ans , f(type == "I" , start , val[rin[*it1]] , curSize1));
else
ans = mult(ans , f(type == "I" , val[rin[*it1]] , start , curSize1));
//cerr << "Ans:" << ans << endl;
curSize1 = *it2 - in[v];
start = val[rin[*it2]];
u = v;
u = p[u];
}
void getS(int u)
{
cout << "s[" << u << "]:" << endl;
for(auto v : s[u])
{
cout << "V:" << v << endl;
}
cout << endl;
}
int main()
{
//cerr << "TUT" << endl;
init();
//cerr << "INIT DONE" << endl;
cin >> n >> q;
for(int i = 0; i < n; i++)
cin >> val[i];
for(int i = 1; i < n; i++)
{
int u , v;
cin >> u >> v;
u--;v--;
g[u].PB(v);
g[v].PB(u);
}
dfs_sz();
dfs_hld();
set<int> pth;
for(int i = 0; i < n; i++)
del(i);
//Reductant code
for(int i = 0; i < n; i++)
{
for(auto iter = s[i].begin(); iter != s[i].end(); iter++)
{
auto iter2 = iter;
iter2++;
if(iter2 == s[i].end())
break;
int u = rin[*iter] , v = rin[*iter2];
update(u , v , -1);
}
}
//End of the reductant code
//cerr << "ON QUERIES" << endl;
int inter = -1;
for(int i = 1; i <= q; i++)
{
if( i % 100 == 0)
cerr << i << endl;
//if(val[1] != 79 || val[0] != 13 || val[0] != 72)
//cerr << val[0] << " " << val[1] << " " << get(0 , 1 , 1) << endl;
string type;
cin >> type;
if(type == "UPDATE")
type = "UPD";
else if(type == "NON-INCREASING")
type = "NI";
else if(type == "NON-DECREASING")
type = "ND";
else if(type == "INCREASING")
type = "I";
else
type = "D";
if(inter == i)
cerr << "TYPE:" << type << endl;
if(type == "UPD")
{
//cout << endl;
//cerr << "UPDATE STARTED" << endl;
int v , value;
cin >> v >> value;
v--;
if(inter == i)
{
cerr << v << " " << value << endl;
}
//cerr << val[v] << " " << value << endl;
if(val[v] == value)
continue;
val[v] = value;
if(value != -1)
{
auto it = s[nxt[v]].lower_bound(in[v] + 1);
//Next in subtree
if(it != s[nxt[v]].end())
{
int u = rin[*it];
if(i == inter)
cerr << u << endl;
//cerr << u << endl;
//cerr << "UPD"
update(u , v , i);//Next - cur
}
if(it == s[nxt[v]].begin())
{
s[nxt[v]].insert(in[v]);
continue;
}
it--;
if(*it == in[v])
{
if(it == s[nxt[v]].begin())
{
s[nxt[v]].insert(in[v]);
continue;
}
it--;
}
int u = rin[*it];
s[nxt[v]].insert(in[v]);
update(v , u , i);
continue;
}
//cerr << "TUT" << endl;
del(in[v]);
s[nxt[v]].erase(in[v]);
auto it = s[nxt[v]].lower_bound(in[v]);
if(it == s[nxt[v]].begin() || it == s[nxt[v]].end())
{
if(it == s[nxt[v]].end())
{
if(it == s[nxt[v]].begin())
continue;
it--;
del23(*it);
continue;
}
if(it == s[nxt[v]].begin())
{
del01(*it);
continue;
}
}
auto it2 = it;
it2--;
update(rin[*it] , rin[*it2] , -1) ;
//cerr << "UPDATE FINISHED" << endl;
continue;
}
int u , v , a , b;
cin >> u >> v >> a >> b;
//cerr << "SECOND TYPE QUERY" << endl;
u--;v--;
if(type == "D")
{
swap(u , v);
type = "I";
}
if(type == "NI")
{
swap(u , v);
type = "ND";
}
if(a > b)
swap(a , b);
int start = a - (type == "I");
int finish = b + (type == "I");
int curSize1 = 0 , curSize2 = 0;
int ans = 1;
while(u != v)
{
if(inter == i)
cerr << u << " " << v << " " << ans << endl;
if(!isIn(v , nxt[u]))
{
//cerr << "HERE" << endl;
push_up(ans , u , nxt[u] , curSize1 , start , type);
continue;
}
if(!isIn(u , nxt[v]))
{
push_up(ans , v , nxt[v] , curSize2 , finish , type , 2);
continue;
}
break;
}
if(u != v)
{
//cerr << "TUT" << endl;
int to = -1;
if(isIn(u , v))
{
to = v;
}
else if(isIn(v , u))
{
to = u;
}
assert(to != -1);
int pushType;
if(nxt[to] == nxt[u] && nxt[to] == nxt[v])
{
pushType = depth[v] > depth[u];
}
else
{
pushType = nxt[v] == nxt[to];
}
//nxt[to] == nxt[u] ? 0 : 1;
//cerr << pushType << " " << to << endl;
//cerr << to << endl;
if(!pushType)
{
if(i == inter)
cerr << "TUT" << " " << to << endl;
push_up(ans , u , to , curSize1 , start , type , 0 , i == inter);
}
else
push_up(ans , v , to , curSize2 , finish , type , 2);
}
else
{
/*for(auto v : s[nxt[u]])
{
cout << "V: " << v << endl;
}*/
//getS(nxt[1]);
push_up(ans , u , u , curSize1 , start , type , 0 , q == 0);
//cerr << curSize1 << " " << curSize2 << endl;
}
ans = mult(ans , f(type == "I" , start , finish , curSize1 + curSize2));
//cerr << "Ans: " << ans << endl;
if(i == inter)
cerr << ans << endl;
cout << ans << endl;
}
//cerr << "DONE" << endl;
}
Time Complexity=O(QLog^2N)
Space Complexity=O(N)
CHEF VIJJU’S CORNER
Why O(N) chunks?
Note on how we defined our “chunks”. We defined our “chunks” as " Something beginning with non-negative W_i, followed by 0 or more -1's and then ending with another non negative value W_j."
The end points may belong to multiple chunks, and thats the case when some node with W_i \geq 0 has multiple children. In this case, each child leads to a unique path and hence a unique chunk. But the number of children is O(N) and edges are also O(N) and cycles are also not allowed, hence construction of the special test case where nodes are interconnected to lead to O(N^2) chunks (and hence requirement of O(N^2) paths intersection at only end points to cover the entire tree) is not possible.
Similarly you can argue about the values in middle of chunks (i.e. -1)
Combinatorics: Why the case of increasing became number of ways to select integers from range(Informal Intuition)
The thing to ask is that, when will 2 cases be different?
In our n \choose r formulas, the order does NOT matter. Now, what the does our n \choose r formula represent? It represents that irrespective of order, there are these many ways to select r things from n objects. Since order does not matter, I can simply put all selected numbers in increasing order - that will be one way.
Now, look at the increasing sequence. No other order or permutation can be increasing, because swapping any value will lead to the sequence to be no longer increasing. Hence, there is only 1 possible order/way-of-putting-the-numbers.
Now, two increasing sequences can be different iff at some index i, seq1[i] \neq seq2[i]. But if that is the case, this means that the numbers selected are different. Had it been the case that some permutation of same selected numbers would have satisfied the conditions, then our formula would go wrong. But we see that only 1 permutation of selected numbers can satisfy the cases, and two sequences can be different only if number selected at some positions are different.
Hence the number of ways to replace the -1 in the chunk increasing order is equal to the number of ways to chose cnt numbers in range [W_i,W_j].
Why storing just the range product can be insufficient
This is a general perspective and may/may-not be applicable to the current problem. As I said, implementations vary.
The thing to note is that, HLD decomposes the tree into disjoint paths such that you can reach root from any vertex in O(LogN) path changes.
Over each (heavy) path/chain we build a segment tree. You must store sufficient parameters such that all cases are handled.
Say I am going from u to LCA(u,v) which are on one path. Lets say that W_{LCA(u,v)}=-1, and that its W_j would be found somewhere down when going from LCA(u,v) to v.
Lets say if I store the number of -1 in prefix/suffix of the chain, I might be able to check if W_{LCA(u,v)}=-1 or not and handle that one case manually. But if all that I stored is the answer, then I might get wrong answers when changing across chains.
Setter's Notes
We can build an HLD there. Then we can split every path into O(log(N))
paths. You can note that only values with A_i not equal to -1 matter.
So we can check whether these values satisfy the non-decreasing
condition. If no then the answer is 0.
Now for every A_i not equal to -1 let’s maintain the number of ways to
change -1 till the next A_i not equal to -1 on its heavy path(This can
be done easily with some binomial coefficients and if we store set of
A_i not equal to -1 on every heavy path) And store this values in
segment tree. For -1 these values should be equal to 1. Now roughly
speaking we can query product on the range in segment tree. And for
most left and rightest A_i on the path we can find the number of ways
to change values of -1 on it and on the previous heavy path by hand
again with some binomial coefficients.
Update : O(log(N))
Query : O(log^2(N))
- Make sure to give this unofficial editorial a read as well as it gives some more perspective on segment tree implementation. With respect to that editorial, answer the following-
- Describe the use of each parameter stored in his segment tree. Don’t tell what it does, tell why it is needed.
- Describe the parent child relationship of his segment tree
- Leave a like at his editorial so he no longer has to ask for sympathy votes