长链剖分
规定若\(x\)为叶结点，则\(len[x]=1\)。
否则定义\(preferredchild[x]\)（以下简称\(pc[x]\)，称\(pc[x]\)为\(x\)的长儿子）为\(x\)的所有子结点\(ver\)中，\(len[ver]\)最大的一个。\(len[x]=len[pc[x]]+1\)。
这里的\(pc[x]\)相当于树链剖分中的\(heavychild[x]\)，类似地，我们可以认为整棵树被划分为了若干条互不相交的长链。
有什么用？
求LCA。
到底有什么用？
优化树形DP。
通过长链剖分，我们可以将一些状态下标为深度的树形DP优化至线性复杂度。
一道例题
给你一棵\(n\)个结点的树，根结点编号为\(1\)。对于每个结点\(x\)，求出以\(x\)为根的子树中到\(x\)路径的长度（边数）为多少的结点数最多，在结点数最多的条件下最小化路径的长度。
\(n \leq 1000000\)。
不准Dsu on Tree！
题解
先考虑普通的树形DP，设状态\(f[x][j]\)表示以\(x\)为根的子树中，到\(x\)距离为\(j\)的结点数。
转移方程显然：
\]
\]
时间复杂度\(O(n^2)\)。
但是对于本题，这样的算法无论时间还是空间都是无法接受的。
考虑优化这个树形DP。
定义\(f[x]\)的有效长度为\(len[x]-1\)，因为对于\(j>len[x]-1\)时，\(f[x][j]\)显然为\(0\)。
如果\(x\)只有一个子结点\(ver\)的话，转移显然为：
\]
\]
这样的转移可以使用指针\(O(1)\)地完成。
\]
\]
可以想到，如果\(x\)的子结点不止一个的话，我们也可以采取相同的方式，即先从\(x\)的所有子结点中选择一个子结点让\(x\) \(O(1)\)“继承”它的状态，其他子结点仍采用DP方法暴力合并。
可以发现，我们在将\(f[ver]\)合并到\(f[x]\)时，时间复杂度是\(O(len[ver])\)的。
为了使时间复杂度达到最优，我们选择继承的那个子结点必然是\(x\)的长儿子\(pc[x]\)，因为根据长儿子的定义，\(f[pc[x]]\)在所有的\(f[ver]\)中有效长度最长，这样继承可以最大程度地减少合并时遍历所带来的程序运行时间。
并且结合上面关于有效长度的叙述，我们还可以使用指针动态分配每个\(f[x]\)的内存。
考虑进行了以上优化后，时间复杂度是多少？
\(O(n)\)。顺便一提，空间复杂度也是\(O(n)\)。
Why？
考虑到每个结点只属于一条长链，且每一条长链只会在链顶处被\(O(len)\)暴力合并一次，所以时间复杂度为\(O(n)\)。
空间复杂度的话，我们发现任意一条长链链顶\(top\)处的\(f[top]\)被分配到的内存必然包含了这条长链上所有的结点被分配到的内存（换句话说，对于同一条长链上的两个结点\(x,y\)，如果\(y\)是\(x\)的祖先，那么\(y\)被分配到的内存必然包含\(x\)被分配到的内存），且每一个\(f[top]\)的有效长度均为\(len[top]-1\)，结合之前所述\(n\)个结点的树被划分为了若干条互不相交的长链，空间复杂度\(O(n)\)得证。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <vector>
#define rin(i,a,b) for(int i=(a);i<=(b);i++)
#define rec(i,a,b) for(int i=(a);i>=(b);i--)
#define trav(i,a) for(int i=head[(a)];i;i=e[i].nxt)
using std::cin;
using std::cout;
using std::endl;
typedef long long LL;
inline int read(){
int x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x;
}
const int MAXN=1000005;
int n;
int ecnt,head[MAXN];
int fa[MAXN],len[MAXN],pc[MAXN];
int ans[MAXN];
int Memory[MAXN],*f[MAXN],*ptr;
struct Edge{
int to,nxt;
}e[MAXN<<1];
inline void add_edge(int bg,int ed){
ecnt++;
e[ecnt].to=ed;
e[ecnt].nxt=head[bg];
head[bg]=ecnt;
}
void dfs1(int x,int pre){
fa[x]=pre;
int maxlen=-1;
trav(i,x){
int ver=e[i].to;
if(ver==pre) continue;
dfs1(ver,x);
if(len[ver]>maxlen){
maxlen=len[ver];
pc[x]=ver;
}
}
len[x]=len[pc[x]]+1;
}
void dfs2(int x,int *ff){
f[x]=ff;
if(pc[x]){
dfs2(pc[x],ff+1);
ans[x]=ans[pc[x]]+1;
if(ans[x]==1&&f[x][ans[x]]==1) ans[x]--;
}
f[x][0]=1;
trav(i,x){
int ver=e[i].to;
if(ver==fa[x]||ver==pc[x]) continue;
int *temp=ptr;
ptr+=len[ver];
dfs2(ver,temp);
rin(j,0,len[ver]-1){
f[x][j+1]+=temp[j];
if(j+1<ans[x]&&f[x][j+1]>=f[x][ans[x]]) ans[x]=j+1;
if(j+1>ans[x]&&f[x][j+1]>f[x][ans[x]]) ans[x]=j+1;
}
}
}
int main(){
n=read();
rin(i,2,n){
int u=read(),v=read();
add_edge(u,v);
add_edge(v,u);
}
dfs1(1,0);
ptr=Memory+len[1];
dfs2(1,Memory);
rin(i,1,n) printf("%d\n",ans[i]);
return 0;
}
还有一种使用\(std::vector\)实现的方法，为了快速继承同样使用了指针。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <vector>
#define rin(i,a,b) for(int i=(a);i<=(b);i++)
#define rec(i,a,b) for(int i=(a);i>=(b);i--)
#define trav(i,a) for(int i=head[(a)];i;i=e[i].nxt)
using std::cin;
using std::cout;
using std::endl;
typedef long long LL;
inline int read(){
int x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x;
}
const int MAXN=1000005;
int n;
int ecnt,head[MAXN];
int fa[MAXN],len[MAXN],pc[MAXN];
int ans[MAXN],realans[MAXN];
std::vector<int> *f[MAXN];
struct Edge{
int to,nxt;
}e[MAXN<<1];
inline void add_edge(int bg,int ed){
ecnt++;
e[ecnt].to=ed;
e[ecnt].nxt=head[bg];
head[bg]=ecnt;
}
void dfs1(int x,int pre){
fa[x]=pre;
int maxlen=-1;
trav(i,x){
int ver=e[i].to;
if(ver==pre) continue;
dfs1(ver,x);
if(len[ver]>maxlen){
maxlen=len[ver];
pc[x]=ver;
}
}
len[x]=len[pc[x]]+1;
}
void dfs2(int x){
if(pc[x]){
dfs2(pc[x]);
f[x]=f[pc[x]];
ans[x]=ans[pc[x]];
if(ans[x]==(int)(*f[x]).size()-1&&(*f[x])[(int)f[x]->size()-1]==1) ans[x]++;
}
else{
f[x]=new std::vector<int>();
}
f[x]->push_back(1);
trav(i,x){
int ver=e[i].to;
if(ver==fa[x]||ver==pc[x]) continue;
dfs2(ver);
rin(j,0,(int)f[ver]->size()-1){
int jj=(int)f[x]->size()-((int)f[ver]->size()+1-j);
(*f[x])[jj]+=(*f[ver])[j];
if(jj>ans[x]&&(*f[x])[jj]>=(*f[x])[ans[x]]) ans[x]=jj;
if(jj<ans[x]&&(*f[x])[jj]>(*f[x])[ans[x]]) ans[x]=jj;
}
}
realans[x]=(int)f[x]->size()-ans[x]-1;
}
int main(){
n=read();
rin(i,2,n){
int u=read(),v=read();
add_edge(u,v);
add_edge(v,u);
}
dfs1(1,0);
dfs2(1);
rin(i,1,n) printf("%d\n",realans[i]);
return 0;
}