(Analysis by Spencer Compton )

Let's think about ways we can embed a tree in a 2D plane such that paths can be covered by exactly two axis-aligned rectangles. One idea that comes to mind is that we might want to split a path into two parts and then use one box to cover one of those parts and another box to cover the other part.

Assume we arbitrarily root the input tree. A natural way to break a tree path into two parts is to break it into two parts such that both parts consist of a vertical chain in the tree (more formally, it contains a subset of the graph that forms one connected component and are all ancestors of one node in the subset). We can split any arbitrary path from $A$ to $B$ by having one path from $A$ to $LCA(A,B)$ (the lowest common ancestor of $A$ and $B$) and another path from $B$ to its ancestor that is one level below $LCA(A,B)$. (A special case is when $A=LCA(A,B)$ and thus the original path is already in the desired form.)

Now, we just need to find a way to embed a tree in a 2D plane such that vertical chains can be covered by one axis-aligned rectangle. Let's consider a recursive embedding. For each node $i$, we will deal with the subtree rooted at $i$. Let $S_i$ be the size of the subtree rooted at $i$. We will make an embedding of $i$'s subtree inside a $S_i \times S_i$ square such that for each node $j$ in $i$'s subtree, the rectangle with $j$ at the bottom-left corner and $i$ at the top-right corner contains exactly the nodes on the path from $i$ to $j$.

As a base-case, it's clear that a leaf node satisfies this constraint no matter how it is embedded (as long as we don't put any two nodes at the same point). Now, let's embed $i$ given that we know how to do an embedding for each of its children's respective subtrees. We will put $i$ at the top-right corner of our $S_i \times S_i$ square. Then, for some child $j$ we will take the $S_j \times S_j$ embedding for it and place it at the top-left corner of our $S_i \times S_i$ square. While $i$ has another child, we will take that child's square embedding and place it so that its top-left corner touches the bottom-right corner of the previous child's square embedding. Conveniently, this embedding of $i$'s subtree satisfies the desired constraints. Based on our embedding, the box with $i$ at the top-right corner and some descendant $j$ at the bottom-left corner will contain exactly the vertical chain from $i$ to $j$. This shows us a method of embedding the tree recursively. We can do this in $O(N)$ time.

Thus, we have $O(N)$ embedding of a tree into the plane. Then, for every query we want to break it into two vertical chains. We can do this as mentioned previously, by calculating LCA in $O(\log{N})$. Our final runtime is $O(N + Q \log{N})$.


using namespace std;
int x;
int y;
int lc;
int sub;
int h;
int dfs(int now, int from){
sub[now] = 1;
lc[now] = from;
if(from==-1){
h[now] = 0;
}
else{
h[now] = h[from]+1;
}
for(int i = 0; i<adj[now].size(); i++){
int to = adj[now][i];
if(to==from){
continue;
}
sub[now] += dfs(to,now);
}
return sub[now];
}
void go(int now, int from, int ylo, int yhi, int xlo, int xhi){
x[now] = xlo;
y[now] = ylo;
setFarmLocation(now,xlo++,ylo++);
for(int i = 0; i<adj[now].size(); i++){
int to = adj[now][i];
if(to==from){
continue;
}
go(to,now,ylo,ylo+sub[to]-1,xhi-sub[to]+1,xhi);
ylo += sub[to];
xhi -= sub[to];
}
}

}
int lca(int a, int b){
if(h[a]<h[b]){
swap(a,b);
}
for(int i = 17; i>=0; i--){
int toa = lc[i][a];
if(toa!=-1 && h[toa]>=h[b]){
a = toa;
}
}
if(a==b){
return a;
}
for(int i = 17; i>=0; i--){
int toa = lc[i][a];
int tob = lc[i][b];
if(toa!=tob){
a = toa;
b = tob;
}
}
return lc[a];
}

void buildFarms(){
dfs(0,-1);
int n = getN();
go(0,-1,1,n,1,n);
for(int i = 1; i<18; i++){
for(int j = 0; j<n; j++){
if(lc[i-1][j]==-1){
lc[i][j] = -1;
}
else{
lc[i][j] = lc[i-1][lc[i-1][j]];
}
}
}
}

void notifyFJ(int a, int b){
int l = lca(a,b);
if(l==b){
return;
}
int ogb = b;

for(int i = 17; i>=0; i--){
int tob = lc[i][b];
if(tob!=-1 && h[tob]>h[l]){
b = tob;
}
}