In this problem, we are given a tree. For each node, we are asked to calculate the minimum number of farmers needed to catch Bessie should she start at that node.

To solve the gold version of this problem (where we are given a fixed starting node for Bessie), it suffices to make the following observation: the number of farmers needed to catch Bessie is the number of nodes which are at least as close to a leaf as to Bessie's starting location, but whose parents are closer to Bessie's starting location than to any leaf. For a justification of this criterion, see the editorial for the gold version of this problem.

To solve the platinum version with only this observation, we would have to make $O(N)$ depth-first searches, a constant number for each possible starting location. This yields an $O(N^2)$ algorithm, which is not fast enough.

Fix some starting node $u$ for Bessie. Let $S_u$ be the set of nodes which are at least as close to a leaf as to the starting node. Then $S_u$ is the union of several disjoint subtrees, and the number of farmers needed is exactly the number of subtrees comprising the set. Unless $u$ is a leaf, there will be multiple subtrees.

Consider any proper subtree of the whole tree; suppose it has $k$ nodes. Then the sum of degrees of all $k$ nodes is $2k-1$, since $k-1$ edges are counted twice and one edge is counted once. Hence the sum over all nodes $v$ in the subtree of $2 - \text{deg}(v)$ is exactly $1$.

The above diversion implies that the number of subtrees comprising $S_u$ is

$$\sum_{v \in S_u} (2 - \text{deg}(v)).$$

Now we seek to maintain the set $S_u$, along with the above sum, as we vary $u$. Fix some arbitrary node to be the "initial" $u$. Every node has some distance-to-nearest-leaf and some distance-to-$u$, and is in the set $S_u$ if and only if the difference between distances is at most $0$. Suppose we depth-first search, changing $u$ as we go. When we traverse an edge from a parent to a child node, the differences of all nodes in the subtree increase by $1$, and the differences of all other nodes in the tree decrease by $1$. When we traverse the same edge in the opposite direction, the opposite happens.

Throughout the depth-first search, we want to maintain a weighted sum over all nodes with nonpositive differences. To do so, we use the following data structure. Compute the inorder traversal of the tree, and divide it into $\sqrt{N}$ blocks. For each block, maintain a Binary Indexed Tree in which a node with weight $w = 2 - \text{deg}(v)$ and difference $d$ contributes $w$ to index $d$ of the BIT.

A subtree corresponds to a range in the inorder traversal. Given an update range, for each block contained entirely within the range, lazily update a counter. For the two blocks cut by the range, rebuild the BITs entirely. And to handle a summation query on the whole data structure, query each block's BIT for a partial sum, taking into account the lazy counter. The complexity of both updates and queries is $O(\sqrt{N} \log N)$. Over the course of the depth-first search we make $O(N)$ updates and queries, yielding an overall time complexity of $O(N \sqrt{N} \log N)$.

#include <iostream> #include <cstdlib> #include <ctime> #include <algorithm> #include <cstdio> #include <fstream> #include <vector> using namespace std; #define MAXN 70500 #define BSIZE 141 #define MAX_BLOCKS 500 vector<int> edges[MAXN]; int distLeaf[MAXN]; int distStart[MAXN]; int startLoc[MAXN], endLoc[MAXN]; int C; void dfsDistances(int i,int par) { distLeaf[i] = MAXN + 1; if(par != -1) distStart[i] = 1 + distStart[par]; else distStart[i] = 0; for(int j=0;j<edges[i].size();j++) if(par != edges[i][j]) { dfsDistances(edges[i][j],i); distLeaf[i] = min(distLeaf[i], 1 + distLeaf[edges[i][j]]); } if(edges[i].size()==1) distLeaf[i] = 0; } void dfsDistances2(int i,int par) { if(par!=-1) distLeaf[i] = min(distLeaf[i],distLeaf[par]+1); for(int j=0;j<edges[i].size();j++) if(par!=edges[i][j]) dfsDistances2(edges[i][j],i); } void dfsOrder(int i,int par) { startLoc[i] = C++; for(int j=0;j<edges[i].size();j++) if(edges[i][j]!=par) dfsOrder(edges[i][j],i); endLoc[i] = C-1; } int val[MAXN],key[MAXN]; int lazy[MAX_BLOCKS]; int overallLazy; int T[MAX_BLOCKS][2*MAXN]; void update(int block,int i,int d) { for(i++;i<2*MAXN;i+=(i&-i)) T[block][i] += d; } long long getSum(int block,int i) { long long c = 0; for(i++;i>0;i-=(i&-i)) c += T[block][i]; return c; } void unbuildBlock(int b,int x,int y) { for(int i=x;i<=y;i++) update(b,key[i],-val[i]); } void rebuildBlock(int b,int x,int y) { for(int i=x;i<=y;i++) update(b,key[i],val[i]); } void updateKey(int low,int high,int dif) { int ilow = low; int ihigh = high; int blockLow = low/BSIZE; int blockHigh = high/BSIZE; if(blockLow == blockHigh) { unbuildBlock(blockLow,low,high); while(low<=high) key[low++] += dif; rebuildBlock(blockLow,ilow,ihigh); return; } unbuildBlock(blockLow,ilow,BSIZE*(ilow/BSIZE) + BSIZE-1); unbuildBlock(blockHigh,BSIZE*(ihigh/BSIZE),ihigh); while(low != (blockLow+1)*BSIZE) key[low++] += dif; while(high != blockHigh*BSIZE-1) key[high--] += dif; rebuildBlock(blockLow,ilow,BSIZE*(ilow/BSIZE) + BSIZE-1); rebuildBlock(blockHigh,BSIZE*(ihigh/BSIZE),ihigh); for(int b=blockLow+1;b<blockHigh;b++) lazy[b] += dif; } long long getTotalSum() { long long sm = 0; for(int b=0;b<MAX_BLOCKS;b++) sm += getSum(b,MAXN-lazy[b]-overallLazy); return sm; } int ans[MAXN]; int N; void dfs(int i,int par) { ans[i] = getTotalSum(); for(int j=0;j<edges[i].size();j++) if(edges[i][j]!=par) { updateKey(startLoc[edges[i][j]], endLoc[edges[i][j]], 2); overallLazy--; dfs(edges[i][j],i); overallLazy++; updateKey(startLoc[edges[i][j]], endLoc[edges[i][j]], -2); } } int main() { int a,b; cin >> N; for(int i=1;i<N;i++) { cin >> a >> b; a--,b--; edges[a].push_back(b); edges[b].push_back(a); } dfsDistances(0,-1); dfsDistances2(0,-1); dfsOrder(0,-1); for(int i=0;i<N;i++) { val[startLoc[i]] = 2 - (int)edges[i].size(); key[startLoc[i]] = distLeaf[i] - distStart[i] + MAXN; } for(int b=0;b<MAX_BLOCKS;b++) rebuildBlock(b,BSIZE*b,BSIZE*(b+1)-1); dfs(0,-1); int mdif = 0; for(int i=0;i<N;i++) { if(edges[i].size()==1) ans[i] = 1; cout << ans[i] << '\n'; } }