一般情况下可以使用长链剖分来优化的 DP 会有一维状态为深度维，我们可以以类似 dsu on tree 的方式去获取子树信息，即先直接获取长链信息，再暴力合并轻链，可以证明复杂度为 \(O(n)\)。
例题：CF1009F
dsu on tree 是 \(O(n \log n)\) 的。其实我们可以考虑 DP，设 \(f_{x,i}\) 表示 \(x\) 子树内距离 \(x\) 为 \(i\) 的节点个数，\(ans_x\) 表示该点的答案。有转移 \(f_{x,i} =\sum f_{v,i-1}\)，朴素 \(O(n^2)\)。我们可以直接让 \(x\) 取得长儿子的 \(f\) 数组，坐标偏移只要用指针维护，然后暴力合并所有轻儿子，复杂度 \(O(n)\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define _int __int128
#define ull unsigned long long
#define pii pair<int,int>
#define fst first
#define scd second
#define pq priority_queue
#define mkp make_pair
#define popcount(x) __builtin_popcount(x)
#define endl '\n'
int n;
const int N = 1e6+10;
vector<int>g[N];
int dep[N],len[N],fa[N],lc[N],ans[N];
int p[N];
int *f[N],*now=p;
void dfs(int x,int f){fa[x]=f;for(auto v:g[x]){if(v==f)continue;dfs(v,x);if(len[v]>len[lc[x]]){lc[x]=v;}}len[x]=len[lc[x]]+1;
}
void dfs2(int x){f[x][0]=1;if(lc[x]){f[lc[x]]=f[x]+1;dfs2(lc[x]);ans[x]=ans[lc[x]]+1;if(f[x][ans[x]]<=1)ans[x]=0;for(auto v:g[x]){if(v==fa[x]||v==lc[x])continue;f[v]=now;now+=len[v];dfs2(v);for(int j=0;j<len[v];j++){f[x][j+1]+=f[v][j];if(f[x][j+1]>f[x][ans[x]]||(f[x][j+1]==f[x][ans[x]]&&j+1<ans[x])){ans[x]=j+1;}}}}
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}dfs(1,0);f[1]=now;now+=len[1];dfs2(1);for(int i=1;i<=n;i++){cout<<ans[i]<<endl;}return 0;
}
P5904 POI2014 HOT-hotel 加强版
询问树上到彼此距离相等的节点三元组个数。
如图，我们记 \(f_{x,j}\) 为 \(x\) 子树内距离 \(x\) 为 \(j\) 的节点个数，\(g_{x,j}\) 为 \(lca(a,b)\) 到 \(x\) 的距离为 \(d-j\) 的 \((a,b)\) 个数，其中 \(d\) 为 \(a\) 和 \(b\) d到 \(lca\) 的距离（必须相同）。
为什么要这样设计呢？若已知 \(g_{x,j}\)，那么从其他子树再找出一个节点距离 \(x\) 为 \(j\)，它距离 \(lca(a,b)\) 就为 \(d\) 了，也就是说三个点到彼此的距离相等。
那么考虑转移，首先依然是继承长儿子的信息，\(f_{lc_{x}}=f_x+1\)，\(g_{lc_{x}}=g_x-1\)，因为距离增加一则 \(d-j\) 减少一位。此时 \(ans\) 要加上 \(g_{x,0}\)，表示 \(x\) 就是第三个点，至于为什么是在合并轻儿子之前加，是因为我们会递归处理轻儿子所以能加到。然后先计算答案再合并轻儿子。此时 \(f_x\) 和 \(g_x\) 都是处理轻儿子 \(v\) 之前所有的子树的值，第一种情况前面出一个，\(v\) 子树出两个，贡献为 \(f_{x,j-1} \times g_{v,j}\)，前一项 \(j-1\) 是因为第二项到 \(v\) 是 \(d-j\)，那到 \(x\) 就是 \(d-(j-1)\)，所以还需要别的子树距离 \(j-1\) 的点。第二种情况前面出一对，\(v\) 子树出一个，贡献为 \(g_{x,j+1} \times f_{v,j}\)。
然后合并子树信息，\(f\) 转移同上一题，\(g\) 有两种情况，一是从 \(v\) 子树里自己来，有 \(g_{v,j} \to g_{x,j-1}\)，二是从 \(v\) 子树取一个，前面取一个，\(f_{x,j+1} \times f_{v,j} \to g_{x,j+1}\)。
那至此就做完了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define _int __int128
#define ull unsigned long long
#define pii pair<int,int>
#define fst first
#define scd second
#define pq priority_queue
#define mkp make_pair
#define popcount(x) __builtin_popcount(x)
#define endl '\n'
int n,md;
const int N = 1e5+10;
vector<int>e[N];
int p[4*N],len[N],lc[N],ans;
int *now=p,*f[N],*g[N];
void dfs(int x,int fa){for(auto v:e[x]){if(v==fa)continue;dfs(v,x);if(len[v]>len[lc[x]])lc[x]=v;}len[x]=len[lc[x]]+1;
}
void dfs2(int x,int fa){f[x][0]=1;if(lc[x]){f[lc[x]]=f[x]+1;g[lc[x]]=g[x]-1;dfs2(lc[x],x);ans+=g[x][0];for(auto v:e[x]){if(v==fa||v==lc[x])continue;f[v]=now;now+=(len[v]<<1);g[v]=now;now+=(len[v]<<1);dfs2(v,x);for(int j=0;j<len[v];j++){if(j)ans+=f[x][j-1]*g[v][j];ans+=g[x][j+1]*f[v][j];}for(int j=0;j<len[v];j++){g[x][j+1]+=f[x][j+1]*f[v][j];if(j)g[x][j-1]+=g[v][j];f[x][j+1]+=f[v][j];}}}
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}dfs(1,0);f[1]=now;now+=(len[1]<<1);g[1]=now;now+=(len[1]<<1);dfs2(1,0);cout<<ans;return 0;
}