题意

这道题题目有点绕，实际就是找出一种方案，使得从根节点出发的路径的最大值最小，答案即该最大值的最小值。

贪心

这道题的先进滑道是可以贪心建造的。

设$dp[x]$为从$x$出发往下的路径在最优情况下的最大值。

对于一个节点$x$，假设它的儿子的子树全部都已经为最优方案，那么为了使$x$出去的路径的最大值最小，对于所有$x$的儿子$y$，一定要把先进滑道通向$dp[y]$最大的儿子，否则$dp[y]$最大的儿子传到$x$的值一定比当前大。

因此一个节点的先进滑道一定是连向dp值最大的儿子。

树形DP

有了上一步的贪心，可以发现，求每个节点的dp值，必须要所有它的儿子的dp值，因此用树形dp求解。

由于一条全是先进滑道的链（以下称作先进链）的权值只能通过该先进链的长度求取，并不能拆成几段分开求解。因此从一个点往下的所有先进链上的点都要存下来。

由于每个点只会向一个儿子连出一条先进边，根据启发式合并的思想，应该把父亲加到儿子的$vector$中，再把父亲指向儿子的$vector$。这样每个点加一条先进边复杂度是$O(1)$的。

但是，如果直接把$vector$中的所有点都把父亲更新一遍，显然会超时。

考虑$b=\lceil \log_2a \rceil$。
在$a=a+1$时，只有$a$为二的幂或零时，$b$才会+1。

因此，我们只需在把离儿子节点距离为$2^k$和$0$的位置的值重新更新给父亲，其它都沿用儿子的dp值即可。

这样每个点都只从$log$个点更新。
总复杂度为$O(n \times log\ n)$。

代码

#include<bits/stdc++.h>
#define M 100005
using namespace std;
void Max(int &a,int b){
    b>a&&(a=b);
}
int hd[M],nxt[M+M],to[M+M],cnte;
void addedge(int a,int b){
    nxt[++cnte]=hd[a];
    to[cnte]=b;
    hd[a]=cnte;
}
int n;
int p[M],dp[M];
vector<int> S[M];
void dfs(int x,int f){
    int Son=0,mx=-1;
    for(int i=hd[x];i;i=nxt[i]){
        int y=to[i];
        if(y==f)continue;
        dfs(y,x);
        if(dp[y]>dp[Son])Son=y;
    }
    for(int i=hd[x];i;i=nxt[i]){
        int y=to[i];
        if(y==f||y==Son)continue;
        Max(mx,dp[y]);
    }
    if(!Son){
        S[x].push_back(0);
        dp[x]=0;
    }
    else {
        p[x]=p[Son];
        dp[x]=max(mx+1,dp[Son]);
        int sz=S[p[x]].size();
        Max(dp[x],S[p[x]][sz-1]+1);//从零更新 
        for(int i=0;(1<<i)<sz;i++)
            Max(dp[x],S[p[x]][sz-1-(1<<i)]+i+2);//从二的幂更新 
        S[p[x]].push_back(mx+1);
    }
}
void init(){
    memset(dp,0,sizeof(dp));
    dp[0]=-1;
    cnte=0;
    for(int i=1;i<=n;i++){
        S[i].clear();
        hd[i]=dp[i]=0;
        p[i]=i;
    }
}
void solve(){
    scanf("%d",&n);
    init();
    for(int i=1;i<n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        addedge(a,b);
        addedge(b,a);
    }
    dfs(1,0);
    printf("%d\n",dp[1]);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}