You want to escape a zoo in the shape of a tree with $n$ nodes. Each node has an animal in it except for the node you are located at initially. Each second you go from the node you are currently on to the next node on the shortest path to the target. Also each second, every animal can either move to any of the neighboring nodes or stay in the same node.
Given $q$ queries each of the form $a$ $b$, where $a$ is the initial node you are located at, and $b$ is the target. Is there a way for the animals to move, and for you to reach $b$ following the shortest path without being on the same node or edge as an animal throughout the whole journey?
The first line of input contains two integers $n$ and $q$ ($1 \leq n,q \leq 2*10^5$), the number of nodes in the tree, and the number of queries, respectively.
The next line contains $n - 1$ integers $p_2, p_3, ..., p_n$ ($1 \leq p_i < i$), meaning there is an edge between node $i$ and node $p_i$.
Each of the next $q$ lines contains two integers $a$ and $b$ $(1 \leq a,b \leq n)$, representing a query.
For each query print "yes"(without quotes) if it's possible to escape, "no"(without quotes) otherwise.
| Input | Output |
|---|---|
6 4 1 2 2 3 3 1 2 5 1 6 1 6 5 Copy
|
yes yes yes no Copy
|
4 4 1 2 3 1 3 2 4 1 4 2 3 Copy
|
yes no no yes Copy
|
If the degree of $b$ is larger than $1$ then all animals can just go through $b$ outside of the path, otherwise, we need to check if there exists a node on the path between $a$ and $b$ whose distance to $b$ is strictly less than $a$.
Let's root the graph at any node with a degree more than $2$, this will prove helpful later.
For each node find the closest node of it's ancestors that has a degree more than $2$, let's call this $mn_i$.
Then the solution is checking the following $4$ cases in turn:
By rooting the graph at a node with the max degree we assure that between any two nodes $a$ and $b$ the LCA if it's not $a$ or $b$, has a degree more than $2$, thus making finding $mn_i$ easier, $mn_i$ is always at least the root. If the graph is a chain, then the first 3 if statements are enough.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());
const int N = 2e5;
int n,q,dis[N],dp[18][N],is[N];
vector<int>g[N];
void dfs(int u,int p,int cur){
if(g[u].size() > 2)cur = u;
is[u] = cur;
dp[0][u] = p;
for(auto i : g[u])
if(i != p){
dis[i] = dis[u] + 1;
dfs(i,u,cur);
}
}
int lca(int u,int v){
if(dis[u] < dis[v])swap(u,v);
for(int i = 17;i + 1;i--)
if(dis[u] - (1<<i) >= dis[v])
u = dp[i][u];
if(u == v)return u;
for(int i = 17;i + 1;i--)
if(dp[i][u] != dp[i][v]){
u = dp[i][u];
v = dp[i][v];
}
return dp[0][u];
}
int dist(int a,int b,int c){return dis[a] + dis[c] - 2*dis[b];}
int main(){
scanf("%d%d",&n,&q);
for(int i = 1,a;i < n;i++){
scanf("%d",&a);
g[a - 1].push_back(i);
g[i].push_back(a - 1);
}
int st = 0;
for(int i = 0;i < n;i++)
if(g[i].size() > g[st].size())
st = i;
dfs(st,-1,-1);
for(int i = 1;i < 18;i++)
for(int j = 0;j < n;j++)
if(dp[i - 1][j] == -1)dp[i][j] = -1;
else dp[i][j] = dp[i - 1][dp[i - 1][j]];
for(int i = 0,a,b;i < q;i++){
scanf("%d%d",&a,&b);
a--;b--;
if(a == b || g[b].size() > 1){
puts("yes");
continue;
}
if(is[b] == -1){
puts("no");
continue;
}
int c = lca(a,b);
puts(dist(a,c,is[b]) > dist(b,is[b],is[b]) ? "yes" : "no");
}
}