垃圾，没有实力！

NATO · 2024-12-23 19:51:34 · 题解

哎哎哎，主播 2200 做 1h，有点耻辱，记录一下。

思路浅析：

首先一眼发现根节点的各个子树独立，算出每个子树的最大时间取个 \max 即可。

考虑一个菊花的情况，发现这个东西实际上相当于一条链上每个点有个蚂蚁。

然后？...主播被创了 1h 呢！

考虑一个子树内的点最后蚂蚁必然都会走一个非根节点的点，故某两个蚂蚁深度只要相同必然撞上。考虑两蚁相撞的代价，考虑此时我任意让一个蚁上去没有任何区别，留下的蚂蚁时间 +1 后继续和其它蚂蚁合并即可，整个子树就可以抽象为上文蚂蚁链。

发现是一个按子树叶节点深度排序后将之前所用最大时间 +1 与当前深度取 \max 的事情，意义既是我不断加入更深的蚂蚁，如果我的深度小于之前蚂蚁链的长度 +1，意味着我会和之前某只蚁冲上，链长 +1，否则链长为我的深度。

时间复杂度 O(n\log n)，瓶颈在于排序。

参考代码：

#include<bits/stdc++.h>
#define INF 214748364719260817ll
#define ll long long
using namespace std;
ll n;
ll head[500005],cnt;
struct ed
{
    ll v,next;
}edge[1000005];
void add(ll u,ll v)
{
    edge[++cnt].v=v;edge[cnt].next=head[u];head[u]=cnt;
    edge[++cnt].v=u;edge[cnt].next=head[v];head[v]=cnt;
}
ll dp[500005],dep[500005],cot;
void dfs(ll id,ll fa)
{
    bool ok=0;
    dep[id]=dep[fa]+1;
    for(ll i=head[id];i;i=edge[i].next)
    {
        ll v=edge[i].v;
        if(v==fa)continue;
        ok=1;
        dfs(v,id);
    }
    if(!ok) dp[++cot]=dep[id];
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    ll u,v;
    for(ll i=1;i<n;++i)cin>>u>>v,add(u,v);
    ll res=0;
    for(ll i=head[1];i;i=edge[i].next)
    {
        ll v=edge[i].v;
        cot=0;
        dfs(v,1);
        sort(dp+1,dp+1+cot);
        ll ans=0;
        for(ll j=1;j<=cot;++j)ans=max(ans+1,dp[j]);
        res=max(res,ans);
    }
    cout<<res<<'\n';
}