Unaccepted 100分求助
  • 板块P3942 将军令
  • 楼主0x386
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/7/4 19:24
  • 上次更新2023/10/27 21:53:18
查看原帖
Unaccepted 100分求助
350444
0x386楼主2022/7/4 19:24
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,u,v,ans,k,t;
int f[N],cnt,fa[N];
bool vis[N],_vis[N];
struct node{
	int id,dep;
	node(){}
	node(const int &_i,const int &_d):id(_i),dep(_d){}
	bool operator >(const node &x)const{
		return dep<x.dep;
	}
};
struct Edge{
	int to,nxt;
	Edge(){}
	Edge(const int &_t,const int &_n):to(_t),nxt(_n){} 
}ed[N<<1];
priority_queue<node,vector<node>,greater<node> > q;
void add(int u,int v){
	ed[++cnt]=Edge(v,f[u]);
	f[u]=cnt;
}
void dfs(int u,int fat,int depth){
	fa[u]=fat;
	q.push(node(u,depth));
	for(int i=f[u];i;i=ed[i].nxt){
		int v=ed[i].to;
		if(v==fat) continue;
		dfs(v,u,depth+1);
	}
}
int _find(int x,int t){
	if(t==k||x==0) return x;
	return _find(fa[x],t+1);
}
void _dfs(int u,int _,int depth){
	if(depth>k) return;
	if(_vis[u]) return;
	vis[u]=_vis[u]=true;
	for(int i=f[u];i;i=ed[i].nxt){
		int v=ed[i].to;
		if(v==_||_vis[v]) continue;
		_dfs(v,_,depth+1);
	}
}
int main(){
//	freopen("P3942_1.in","r",stdin);
	cin>>n>>k>>t;
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs(1,0,1);
	while(!q.empty()){
		int p=q.top().id;
//		cout<<q.top().dep<<endl;
		q.pop();
		if(vis[p]) continue;
		memset(_vis,false,sizeof(_vis));
		int gf=_find(p,0);
		_dfs(gf+(gf==0),gf+(gf==0),0);
		ans++;
	}
	cout<<ans;
	return 0;
}
2022/7/4 19:24
加载中...