最近遇到了很多次这个trick，所以写个博客记录一下。
P2018 消息传递
but \(n\le2e5\)
先考虑根固定的情况，设 \(f_x\) 表示以 \(x\) 为根的子树全部传达需要的时间，一个很显然的思路是先去 \(x\) 的子节点中 \(f\) 值最大的节点，这样能尽可能让每一刻传递信息的节点尽量多。时间复杂度是 \(O(NlogN)\)，但是要对每一个点做一次，复杂度是我们不能接受的。
考虑换根dp，我们想要转移答案，就需要先处理出当前节点除去某个子节点后的 \(f\) 值，在删除某一个节点时，在它之前被选的节点不会受到影响，而在它之后被选的节点会整体提前一个单位时间，所以我们记录一个前缀max和后缀max，那删除某一个子节点y后的 \(f\) 值，就是前缀max和后缀max+1中的较大值，到这里换根dp的实现就很明显了。
vector<int> e[N],t[N],pre[N],suf[N];
void dfs(int x,int fa){for(int i=0;i<e[x].size();i++){int y=e[x][i];if(y==fa)continue;dfs(y,x);t[x].push_back(f[y]);}sort(t[x].begin(),t[x].end());int ans=0;pre[x].resize(t[x].size());suf[x].resize(t[x].size());for(int i=0;i<t[x].size();i++){if(i==0)pre[x][i]=t[x][i]+t[x].size()-i;else pre[x][i]=max(t[x][i]+(int)t[x].size()-i,pre[x][i-1]);ans=max(ans,t[x][i]+((int)t[x].size()-i));}f[x]=ans;for(int i=t[x].size()-1;i>=0;i--){if(i==t[x].size()-1)suf[x][i]=t[x][i]+t[x].size()-i;else suf[x][i]=max(suf[x][i+1],t[x][i]+(int)t[x].size()-i);}
}
void exc(int x,int fa){int ans=0;sort(t[x].begin(),t[x].end());pre[x].resize(t[x].size());suf[x].resize(t[x].size());for(int i=0;i<t[x].size();i++){if(i==0)pre[x][i]=t[x][i]+t[x].size()-i;else pre[x][i]=max(t[x][i]+(int)t[x].size()-i,pre[x][i-1]);ans=max(ans,t[x][i]+((int)t[x].size()-i));}g[x]=ans;for(int i=t[x].size()-1;i>=0;i--){if(i==t[x].size()-1)suf[x][i]=t[x][i]+t[x].size()-i;else suf[x][i]=max(suf[x][i+1],t[x][i]+(int)t[x].size()-i);}for(int i=0;i<e[x].size();i++){int y=e[x][i];if(y==fa)continue;int p=lower_bound(t[x].begin(),t[x].end(),f[y])-t[x].begin();int num=0;if(p>0)num=max(num,pre[x][p-1]-1);if(p<t[x].size()-1)num=max(num,suf[x][p+1]);g[y]=max(f[y],num+1);t[y].push_back(num);exc(y,x);}
}
在换根dp时，这种记录前缀后缀来消除某个节点的trick是很常用的