PROBLEM LINK:
Author: Ritesh Gupta
Tester: Raja Vardhan Reddy
Editorialist: Akash Bhalotia
DIFFICULTY:
Medium
PREREQUISITES:
Lowest Common Ancestor, Depth-First Search, Dynamic Programming.
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,
- If it strictly increases first, up to a certain node in the path and then decreases till it reaches v, or
- If it strictly increases till we reach v, or
- 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,
-
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,
-
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,
-
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,
-
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:
-
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.
-
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;
vector<int> adj[N];
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];
for(auto x:adj[root])
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];
for(int u:adj[v])
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++)
{
adj[i].clear();
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--;
adj[u].pb(v);
adj[v].pb(u);
}
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 comment(linker, "/stack:200000000")
//#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];
vector<vi>adj(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;
rep(i,adj[u].size()){
if(adj[u][i]!=p)
dfs(adj[u][i],u,l+1);
}
}
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){
adj[i].clear();
}
rep(i,n-1){
cin>>u>>v;
u--;
v--;
adj[u].pb(v);
adj[v].pb(u);
}
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
{
Reader r=new Reader();
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;
edge[u].add(v);
edge[v].add(u);
}
for(i=0;i<N;i++) a[i]=r.nextInt();
DFS(0,0);
while (Q-->0) //answering queries
{
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);
}
static class Reader
{
final private int BUFFER_SIZE = 1 << 16;private DataInputStream din;private byte[] buffer;private int bufferPointer, bytesRead;
public Reader(){din=new DataInputStream(System.in);buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
}public Reader(String file_name) throws IOException{din=new DataInputStream(new FileInputStream(file_name));buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
}public String readLine() throws IOException{byte[] buf=new byte[64];int cnt=0,c;while((c=read())!=-1){if(c=='\n')break;buf[cnt++]=(byte)c;}return new String(buf,0,cnt);
}public int nextInt() throws IOException{int ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;
}public long nextLong() throws IOException{long ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;
}public double nextDouble() throws IOException{double ret=0,div=1;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c = read();do {ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(c=='.')while((c=read())>='0'&&c<='9')ret+=(c-'0')/(div*=10);if(neg)return -ret;return ret;
}private void fillBuffer() throws IOException{bytesRead=din.read(buffer,bufferPointer=0,BUFFER_SIZE);if(bytesRead==-1)buffer[0]=-1;
}private byte read() throws IOException{if(bufferPointer==bytesRead)fillBuffer();return buffer[bufferPointer++];
}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 