# CHEFTRIP - Editorial

Author: Ritesh Gupta
Tester: Raja Vardhan Reddy
Editorialist: Akash Bhalotia

Medium

### PROBLEM:

Given a tree with N vertices, each having a value A_i, find if the sequence formed by the path from a query vertex x_1 to a query vertex x_L holds the property: A_{x_1}<A_{x_2}<…<A_{x_p}>…>A_{x_{L−1}}>A_{x_L} for some integer p (1 \le p \le L).

### HINTS:

Not the full solution. Just some hints to help you if you are stuck at some point. As soon as you encounter a hint that you had not thought of, try solving the problem on your own.

Hint 1:

The graph is a tree. There will be a unique path from a node to any other node. If we root the tree, the path will pass through the LCA of the two nodes. What useful information can you store for each node related to its ancestors, which will help you to determine the nature of the path from the node to its ancestors?

Hint 2:

For each node u, store two values: posInc[u] and posDec[u].

posInc[u] stores the furthest ancestor of u for which the sequence increases on the path from u to it, but then either decreases, or remains the same for the ancestor above it.

Similarly, posDec[u] stores the furthest ancestor of u for which the sequence decreases on the path to it, but then increases or has the same value for its ancestor.

How can you utilise these values to determine the nature of the path between query vertices?

### QUICK EXPLANATION:

show

Root the tree, and for every vertex u, find its furthest ancestor (closest to the root) for which the sequence increases on the path from u to it, but then decreases or remains the same for the ancestor above it. Also find u's furthest ancestor for which the sequence decreases on the path from u to it, but then starts to increase or remains the same for the ancestor above it. These can be computed using DFS. Now, to answer the queries, use this information, along with the LCA of the nodes to examine the nature of the path and determine whether or not it is beautiful.

### EXPLANATION

show

The sequence of numbers in a path from nodes u to v is beautiful,

1. If it strictly increases first, up to a certain node in the path and then decreases till it reaches v, or
2. If it strictly increases till we reach v, or
3. It strictly decreases till we reach v.

As the graph is a tree, there is a unique path from any node to any other node. Let’s root the tree at node 1. Since we have rooted the tree, the path from any node to any other node will pass through the Lowest Common Ancestor of the two nodes in the tree. You can learn about LCA from some of these tutorials: [1], [2], [3], [4].

Let’s use dynamic programming to store some useful information about a node and its ancestors.

For every node u, let’s compute two values: posInc[u] and posDec[u]. posInc[u] stores the furthest ancestor (closest to the root) of u, such that the sequence from u to posInc[u] is strictly increasing, but either decreases or remains the same on going above it. Similarly, posDec[u] stores the furthest ancestor of u such that the sequence from u to posDec[u] is strictly decreasing, but increases or remains the same on going above it. (Note that u is also an ancestor of u.)

As this information is related to a node and its ancestors, we can easily compute this using DFS. We run a DFS from node 1, and compute these values for all the nodes as follows:

Let p be the parent of u in the tree. Then,

If A_u=A_p,

• posInc[u]=posDec[u]=u.

As the sequence neither increases nor decreases when we go above u, thus, u is the furthest ancestor of u for which the sequence strictly increases and then stops following this property, as well as the furthest ancestor of u for which the sequence strictly decreases and then stops following this property. (Note that this case will also be applicable for the root node).

If A_u \lt A_p,

• posInc[u]=posInc[p]
• posDec[u]=u

As A_u \lt A_p, the sequence is increasing from u to p. Thus, the furthest ancestor after which the sequence stops strictly increasing will be stored in posInc[p]. Note that since u is a child of p, the DFS function for it was called after being called for p. Thus, this value posInc[p] had already been computed, when DFS was called for p.

As A_u \lt A_p, the sequence stops decreasing when we go up from u. Thus, u is its furthest ancestor after which the sequence stops strictly decreasing.

Finally, if A_u \gt A_p,

• posInc[u]=u
• posDec[u]=posDec[p]

As A_u \gt A_p, the sequence stops strictly increasing when we go up from u. Thus, u is its furthest ancestor after which the sequence stops strictly increasing.

As A_u \gt A_p, the sequence is strictly decreasing from u to p, i.e., it is following the property. Thus, the furthest ancestor of u after which the sequence stops following this must be stored in posDec[p]. As p is the parent of u, we already have the value of posDec[p].

Thus, posInc[u] and posDec[u] tell us the furthest ancestors of u after which the sequence stops strictly increasing and stops strictly decreasing, respectively.

Let’s now see how to answer queries using the information we have computed above.

A query asks us whether or not the path from a vertex u to a vertex v is beautiful. This means that the sequence from u to a certain node in the path from u to v must be strictly increasing, and the sequence from v to that node must also be strictly increasing. To answer this,

We first compute the LCA of u and v nodes. Then,

1. If posInc[u] is an ancestor of lca, (implies that the sequence from u to lca is strictly increasing) and posInc[v] is also and ancestor of lca (implies that the sequence from v to lca is also strictly increasing), then the path is beautiful. This is because the furthest ancestors of u and v respectively, above which the sequence starts to decrease or have equal value, are located above the lca in the tree. Else,

2. If only posInc[u] is an ancestor of lca, i.e., the sequence increases from u to lca, then it can also happen that the sequence increases till a node between lca and v and then decreases. Let p be the furthest ancestor (closest to the root) of v after which the sequence stops increasing. Thus, p=posInc[v]. So, we need to check if posDec[p] is an ancestor of lca or not. In other words, we check if the furthest ancestor of p after which the sequence starts increasing lies above or at lca or not. If it does, then the path is beautiful, else it is not. Else,

3. If only posInc[v] is an ancestor of lca, i.e., the sequence increases from v to lca, then it can also happen that the sequence increases till a node between u and lca. Thus, we check this. Let p be the furthest ancestor of u after which the sequence stops increasing. Thus, p=posInc[u], and we check if the sequence from p to lca strictly decreases or not, i.e., if posDec[p] is an ancestor of lca or not. If this is true, then the sequence is beautiful, else it is not. Else,

4. The sequence is not beautiful, as it stops increasing from u before reaching lca and it stops increasing from v before reaching lca.

Thus, to solve the problem:

1. Pre-compute the values of posInc[u] and posDec[u], the furthest ancestors (closest to the root) of every vertex u such that the sequence on path from u to posInc[u] is strictly increasing, but then decreases or remains same, and the sequence on the path from u to posDec[u] is strictly decreasing, but then does not follow this for the node above it.

2. To answer the queries, find the LCA of the two nodes, and then check the nature of the path using posInc and posDec to determine whether or not it is beautiful.

### TIME COMPLEXITY:

show

The time complexity, using the binary-lifting implementation of LCA is: O((N+Q)logN), per test case.

Why?

Pre-computing the ancestor table for every results in a complexity of O(NlogN), while answering queries takes \$O(logN)\$per query, as we are finding the LCA of the two vertices every time.

Thus, the total time complexity is: O((N+Q)logN)
The space complexity is: O(NogN), for logN ancestors of each node.

### SOLUTIONS:

Setter
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define endl "\n"

char input[] = "input/input00.txt";
char output[] = "output/output00.txt";

const int N = 100010;
const int level = ceil(log2(N));
int tin[N], tout[N];
int timer;
bool vis[N];
int node[100010][3],up[N][level+1];

void dfs2(int root, int par)
{
vis[root]=true;
if(node[par][0]>node[root][0])
node[root][2]=node[par][2];
else if(node[par][0]<node[root][0])
node[root][1]=node[par][1];
if(!vis[x])
dfs2(x, root);
}

bool is_ancestor(int u, int v)
{
return tin[u]<=tin[v]&&tout[u]>=tout[v];
}

void dfs(int v, int p)
{
tin[v]=++timer;
up[v][0]=p;
for(int i=1; i<=level; i++)
up[v][i]=up[up[v][i-1]][i-1];
if(u!=p)
dfs(u, v);
tout[v]=++timer;
}

int LCA(int u, int v)
{
if(is_ancestor(u, v))
return u;
if(is_ancestor(v, u))
return v;
for(int i=level; i>=0; i--)
if(!is_ancestor(up[u][i], v))
u=up[u][i];
return up[u][0];
}

void pre(int root, int n)
{
for(int i=0;i<=n;i++)
{
tin[i] = tout[i] = 0;

for(int j=0; j<=level; j++)
up[i][j]=0;
}

timer=0;

dfs(root, root);
}

bool check(int u, int v)
{
int lca=LCA(u, v);
if(node[u][2]==node[v][2])
return true;
else if(node[u][1]==node[lca][1] and node[v][2]==node[lca][2])
return true;
else if(node[u][2]==node[lca][2] and node[v][1]==node[lca][1])
return true;
else if(node[u][2]==node[lca][2] and node[node[v][2]][1]==node[lca][1])
return true;
else if(node[v][2]==node[lca][2] and node[node[u][2]][1]==node[lca][1])
return true;
return false;
}

void solve()
{
int n,q;
cin>>n >> q;
for(int i=0;i<=n;i++)
{
vis[i] = false;
node[i][0] = node[i][1] = node[i][2] = 0;
}
for(int i=0; i<n-1; i++)
{
int u, v;
cin>>u>>v;
u--, v--;
}
for(int i=0; i<n; i++)
{
int x;
cin>>x;
node[i][0] = x;
node[i][1] = node[i][2] = i;
}
pre(0, n);
dfs2(0, 0);
while(q--)
{
int u, v;
cin>>u>>v;
u--, v--;
if(check(u, v))
cout<<"1";
else
cout<<"0";
}
cout << endl;
}

int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;
while(t--)
solve();
return 0;
}
Tester
//raja1999

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

//std::ios::sync_with_stdio(false);
int lev[100005],a[100005],par[100005][21],pari[100005],pard[100005];
int dfs(int u,int p,int l=0){
lev[u]=l;
if(p==-1){
pard[u]=u;
pari[u]=u;
}
else{
if(a[u]<a[p]){
pari[u]=pari[p];
pard[u]=u;
}
else if(a[u]>a[p]){
pari[u]=u;
pard[u]=pard[p];
}
else{
pari[u]=u;
pard[u]=u;
}
}
par[u][0]=p;
int i;
}
}
int lca(int u,int v){
if(lev[u]<lev[v]){
swap(u,v);
}
int i;
fd(i,19,0){
if(lev[u]-(1<<i)>=lev[v]){
u=par[u][i];
}
}
if(u==v){
return u;
}
fd(i,19,0){
if(par[u][i]!=par[v][i]){
u=par[u][i];
v=par[v][i];
}
}
return par[u][0];
}
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n,q,u,v,x,y,p,l,i,j;
cin>>n>>q;
rep(i,n){
}
rep(i,n-1){
cin>>u>>v;
u--;
v--;
}
rep(i,n){
cin>>a[i];
}
dfs(0,-1);
f(j,1,20){
rep(i,n){
if(par[i][j-1]==-1){
par[i][j]=-1;
}
else{
par[i][j]=par[par[i][j-1]][j-1];
}
}
}
rep(i,q){
cin>>x>>y;
x--;
y--;
l=lca(x,y);
if(lev[pari[x]]<=lev[l]){
if(lev[pari[y]]<=lev[l]){
cout<<"1";
}
else{
p=pari[y];
if(lev[pard[p]]<=lev[l]){
cout<<"1";
}
else{
cout<<"0";
}
}
}
else{
p=pari[x];
if(lev[pard[p]]>lev[l]){
cout<<"0";
}
else{
if(lev[pari[y]]<=lev[l]){
cout<<"1";
}
else{
cout<<"0";
}
}
}
}
cout<<endl;
}
return 0;
}
Editorialist
//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
private static int tin[], tout[], timer=0,N, logN, anc[][];
private static ArrayDeque<Integer> edge[];
private static int[] ancInc, ancDec, a;

//finding the values of posInc and posDec for u
private static void assignIncDec(int u, int p)
{
if(a[u]==a[p]) ancInc[u]=ancDec[u]=u;
else if(a[u]<a[p])
{
ancInc[u]=ancInc[p];
ancDec[u]=u;
}
else
{
ancInc[u]=u;
ancDec[u]=ancDec[p];
}
}
private static void DFS(int u, int p)
{
tin[u]=timer++;
anc[u][0]=p;

assignIncDec(u,p);

for(int i=1;i<=logN;i++) //calculating ancestors of u
anc[u][i]=anc[anc[u][i-1]][i-1];

for(int v:edge[u])
{
if(v==p) continue;
DFS(v,u);
}

tout[u]=timer++;
}

//is u an ancestor of v?
private static boolean isAncestor(int u, int v)
{
return tin[u]<=tin[v]&&tout[v]<=tout[u];
}
private static int LCA(int u, int v) //returns the LCA of u and v
{
if(isAncestor(u,v)) return u;
if(isAncestor(v,u)) return v;

for(int i=logN;i>=0;i--)
{
if (!isAncestor(anc[u][i], v))
u = anc[u][i];
}
return anc[u][0];
}
private static void init()
{
logN=Integer.numberOfTrailingZeros(Integer.highestOneBit(N));
tin=new int[N];
tout=new int[N];
anc=new int[N][logN+1];
ancInc=new int[N];
ancDec=new int[N];
a=new int[N];
}
public static void main(String[] args) throws IOException
{

int i;

int T=r.nextInt();
StringBuilder sb=new StringBuilder();

while(T-->0)
{
N=r.nextInt();
int Q=r.nextInt();

edge=new ArrayDeque[N];
for(i=0;i<N;i++) edge[i]=new ArrayDeque<>();
init();

for(i=0;i<N-1;i++)
{
int u=r.nextInt()-1;
int v=r.nextInt()-1;

}

for(i=0;i<N;i++) a[i]=r.nextInt();

DFS(0,0);

{
int u=r.nextInt()-1;
int v=r.nextInt()-1;

int lca=LCA(u,v);

//is sequence from u to lca strictly increasing?
if(isAncestor(ancInc[u],lca))
{
//is sequence from v to lca also strictly increasing?
if(isAncestor(ancInc[v],lca)) sb.append(1);
else
{
//is sequence from u to p strictly increasing?
int p=ancInc[v];
if(isAncestor(ancDec[p],lca)) sb.append(1);
else sb.append(0);
}
}

//is sequence from v to lca strictly increasing?
else if(isAncestor(ancInc[v],lca))
{
//is sequence from v to p strictly increasing?
int p=ancInc[u];
if(isAncestor(ancDec[p],lca)) sb.append(1);
else sb.append(0);
}
else sb.append(0);
}
sb.append("\n");
}
System.out.println(sb);
}
{
final private int BUFFER_SIZE = 1 << 16;private DataInputStream din;private byte[] buffer;private int bufferPointer, bytesRead;
}public void close() throws IOException{if(din==null) return;din.close();}
}
}

Feel free to share your approach if it differs. You can ask your doubts below. Please let me know if something’s unclear. I would LOVE to hear suggestions

6 Likes

I used a different approach, that involves finding out the number of “turns” in the path.

A turn is calculated for 3 consecutive nodes: say the 3 nodes have values x, y, z.
These 3 nodes will form a turn, if either x < y > z or x > y < z.

Each node stores the number of turns in the path from the root leading up to that node (for each 3-tuple of consecutive nodes).
A path is beautiful, if the number of turns = 1 and value[u] < value[node_after_u] or the number of turns = 0.

To find out LCAs, I used a segment-tree on the height array, instead the binary-lifting LCA mentioned in this post.

My solution’s complexity is the same as the one given (but may have a higher constant factor).

Aaaand, my Java solution got a TLE.

The funny part is, an accepted C++ solution I downloaded, is taking slightly more time to execute on a large data-set than my Java solution, on my laptop.

Here’s the stats:

Data-set: T = 1, N = 10^5, Q = 10^5

Rushils-MacBook-Pro:may2020_cookoff rushipau\$ time java CHEFTRIP < large_in > out

real 0m1.006s
user 0m2.003s
sys 0m0.204s

Rushils-MacBook-Pro:may2020_cookoff rushipau\$ time ./sol < large_in > ans

real 0m1.164s
user 0m1.153s
sys 0m0.006s

@admin @akashbhalotia Do you have any comments for my findings? (I can send the data-set I used over if required)

thanks

(Having just joined the site, I’ve been trying some recent contest problems for practice…)

My accepted solution never finds the LCA (except by co-incidence or due to the nature of the query). As there are O(n) links, that implies O(n) operations in the DFS. Queries use only information that has already been recorded implying O(1) operations for each query. I think this gives time complexity of O(n+q), albeit with a non-negligible constant factor (in part due to choice of language…), which results in taking more than half the allowed time limit for the test cases.

I borrowed from the editorial’s ideas to use DFS to build a tree from an arbitrarily-selected root with information recorded in it so that any pair of nodes can be checked in constant time to see if one is an ancestor of the other, and the furthest ancestor that can be reached in a constant ascent or descent (“peak” and “valley” ancestors) is also already recorded.

The “Check” function then uses ONLY the recorded information, and only a refers to at most a constant number of nodes (at least 2 and at most 5) to make the decision.

In cases where, both query nodes have the same ancestor peak, we know the path is “beautiful” without specifically finding which node is the peak of the path from A to B.

In cases where neither of the ancestor peaks reached from A or B is the ancestor of the other, we know the path is NOT “beautiful” without specifically finding the LCA (which must be somewhere beyond the next valley(s) following each peak).

In other cases, when a “beautiful” path is found, the LCA becomes known (or trivially knowable) as a side-effect, but otherwise we usually never discover (nor need to discover) the LCA.

Is the O(n+q) solution something that the setter, tester, and editorialist all missed as they were all figuring “LCA algorithm in my toolbox seems relevant; I’ll use it now”, or is there an edge case (not covered in the test cases) that would cause my approach to fail?

@akashbhalotia Why would my Java solution time out when it is actually taking lesser time than some accepted C++ solution on a data set with the largest constraints (on my laptop) ?