题意：

求每棵子树中深度为k的子孙最多的k，有多个k取最小。

做法：

显然的DP是 $ f[i][j] $ 表示在i的子树内深度为j的点的个数，然而这样是 $ O(n^2) $ 的。

由于这道题与深度有关，所以考虑长链剖分。对于长链，直接继承孩子在长链上的答案。对于长链顶点，暴力向上DP转移，所以空间和时间复杂度都为所有长链的长度和，是 $ O(n) $ 的。

#include
    
     #define pb push_back#define rep(i,a,b) for(int i=(a),i##ed=(b);i<=i##ed;i++)#define per(i,a,b) for(int i=(a),i##ed=(b);i>=i##ed;i--)using namespace std;const int N=1000010;int n; vector
     
       e[N];int dep[N],son[N],ans[N];int f[N],dfn[N],idx,tp;int Max(int x,int y) { return x>y? x:y; }void dfs1(int u,int ff) {    dep[u]=1;    rep(i,0,e[u].size()-1) {        int v=e[u][i]; if(v==ff) continue;        dfs1(v,u),dep[u]=Max(dep[u],dep[v]+1);        if(dep[son[u]]
      
       f[dfn[u]+ans[u]]||              (j+1