E1. Distance Tree (easy version)（思维 + 二分 + bfs）

题目链接

试一下呀 ~

哎，还以为能独立写个这么难的题呢~ ~高估自己了T~T
不过还是学到了很多~分析问题上有提高
wa写麻了....没有考虑全....

首先二分是肯定可以的，直接二分答案

一开始的想法：太复杂了...

没有想到连接[1,u]之后深度>=u的点也是可能通过u使得到1的距离变短的...

这样就要转换一下思维了：
对于可以加的边权x，我们二分出了最优答案mid，
贪心的想，首先一定是要使得深度最大的点距离变短，最多最多就是mid；
那么我们可以从深度最大的点向上跳mid-x下到达点u，然后再从u这个点，用x的情况下去bfs所有点；
最后判断一下所有点的深度是否都<=mid就行

int dep[maxn];  //每个点到根节点的距离
int h[maxn],ne[maxn],e[maxn],idx;   //树
int maxi,maxi_idx;  //最深的深度 和 点
int f[maxn];    //记一下每个点的父节点
int n;

void add(int a,int b)
{
    e[idx]=b; ne[idx]=h[a]; h[a]=idx++;
}

void bfs(int u)
{
    queue<int> q;
    dep[u] = 0;
    q.push(u);
    f[u] = -1;

    while(q.size())
    {
        int no = q.front();
        q.pop();

        for(int i=h[no];i!=-1;i=ne[i])
        {
            int j = e[i];

            if(dep[j] != -1) continue;

            dep[j] = dep[no] + 1;
            f[j] = no;

            q.push(j);  
        }
    }
}


bool check(int mid,int x)
{
    int now = maxi_idx;
    for(int i=1;i<=mid-x;i++) now = f[now];

    int tdep[maxn];
    for(int i=1;i<=n;i++) tdep[i] = dep[i];

    tdep[now] = x;

    queue<int> q;
    q.push(now);

    while(q.size())
    {
        int no = q.front();
        q.pop();

        if(tdep[no] > mid) return false;

        for(int i=h[no];i!=-1;i=ne[i])
        {
            int j = e[i];

            if(tdep[j] > tdep[no] + 1)
            {
                tdep[j] = tdep[no] + 1;
                q.push(j);
            }
        }
    }

    for(int i=1;i<=n;i++)
        if(tdep[i] > mid) return false;

    return true;
}

void solve()
{
    memset(h,-1,sizeof h);
    memset(dep,-1,sizeof dep);

    cin>>n;

    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;

        add(a,b);
        add(b,a);
    }

    bfs(1); //求一下深度

    maxi = maxi_idx = 0;    //求一下深度最深的点
    for(int i=1;i<=n;i++)   
        if(dep[i] > maxi)
        {
            maxi = dep[i];
            maxi_idx = i;
        }

    for(int x=1;x<=n;x++)
    {
        if(x >= maxi)   //不会更优了
        {
            cout<<maxi<<' ';
            continue;
        }

        int l=x,r=maxi;
        int ans;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(check(mid,x)) r = mid;
            else l = mid + 1;
        }

        cout<<r<<' ';
    }

    cout<<endl;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }

    return 0;
}