长链剖分
规定若(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
",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
",realans[i]);
return 0;
}