专栏文章

垃圾，没有实力！

NNATO
CF622E题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miqorrn2
此快照首次捕获于
2025/12/04 08:16
3 个月前
此快照最后确认于
2025/12/04 08:16
3 个月前
查看原文
哎哎哎，主播 2200 做 1h，有点耻辱，记录一下。

思路浅析：

首先一眼发现根节点的各个子树独立，算出每个子树的最大时间取个 max⁡\max 即可。
考虑一个菊花的情况，发现这个东西实际上相当于一条链上每个点有个蚂蚁。
然后？...主播被创了 1h 呢！
考虑一个子树内的点最后蚂蚁必然都会走一个非根节点的点，故某两个蚂蚁深度只要相同必然撞上。考虑两蚁相撞的代价，考虑此时我任意让一个蚁上去没有任何区别，留下的蚂蚁时间 +1+1 后继续和其它蚂蚁合并即可，整个子树就可以抽象为上文蚂蚁链。
发现是一个按子树叶节点深度排序后将之前所用最大时间 +1+1 与当前深度取 max⁡\max 的事情，意义既是我不断加入更深的蚂蚁，如果我的深度小于之前蚂蚁链的长度 +1+1，意味着我会和之前某只蚁冲上，链长 +1+1，否则链长为我的深度。
时间复杂度 O(nlog⁡n)O(n\log n)，瓶颈在于排序。

参考代码：

CPP
#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';
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...