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})$.

#include "grader.h"
using namespace std;
int x[100000];
int y[100000];
vector<int> adj[100000];
int lc[18][100000];
int sub[100000];
int h[100000];
int dfs(int now, int from){
	sub[now] = 1;
	lc[0][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];
	}
}
void addRoad(int a, int b){
	adj[a].push_back(b);
	adj[b].push_back(a);
	
}
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[0][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);
	addBox(x[l],y[l],x[a],y[a]);
	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;
		}
	}
	addBox(x[b],y[b],x[ogb],y[ogb]);
}