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]); }