90pts MLE...
  • 板块P3942 将军令
  • 楼主d909RCA
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/3/31 10:57
  • 上次更新2024/3/31 12:49:04
查看原帖
90pts MLE...
703115
d909RCA楼主2024/3/31 10:57
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define Ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,m,t,i,dep[100009],v[100009],ans,fa[100009],r[100009];
vector<int> g[100009];
priority_queue <pair<int,int> > q;
queue <pair<int,int> > q2;
void dfs(int x,int d)
{
	dep[x]=d;
	q.push({d,x});
	for(int i:g[x])
	{
		if(!v[i])
		{
			v[i]=1;
			fa[i]=x;
			dfs(i,d+1);
			v[i]=0;
		}
	}
}
void bfs(int x)
{
	q2.push({x,m});
	pair<int,int> l;
	while(!q2.empty())
	{
		l=q2.front();
		q2.pop();
		if(l.second==-1) continue ;
		v[l.first]=l.second;
		for(int i:g[l.first])
		{
			q2.push({i,l.second-1});
		}
	}
}
signed main()
{
	int x,y;
	cin>>n>>m>>t;
	for(i=1;i<n;++i)
	{
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	v[1]=1;
	dfs(1,1);
	v[1]=0;
	memset(v,-1,sizeof(v));
	int l;
	pair<int,int> b;
	while(!q.empty())
	{
		b=q.top();
		q.pop();
		if(v[b.second]!=-1) continue ;
		l=b.second;
		for(i=1;i<=m&&fa[l]!=0;++i)
		{
			l=fa[l];
		}
		if(r[l]) continue ;
		bfs(l);
		r[l]=1;
		ans++;
	}
	cout<<ans<<endl;
	return 0;
}
2024/3/31 10:57
加载中...