95分求助,第四组我36 ,answer是37
  • 板块P3942 将军令
  • 楼主qwq2519
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/11/10 10:20
  • 上次更新2023/11/5 08:20:57
查看原帖
95分求助,第四组我36 ,answer是37
141335
qwq2519楼主2020/11/10 10:20
#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
typedef  long long lxl;
using namespace std;
inline char gt()
{
//	return getchar();
	static char buf[1<<21],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
template <typename T>
inline void  read(T &x)
{
	register char ch=gt();
	x=0;
	int w(0);
	while(!(ch>='0'&&ch<='9'))w|=ch=='-',ch=gt();
	while(ch>='0'&&ch<='9')x=x*10+(ch&15),ch=gt();
	w?x=~(x-1):x;
}
template <typename T>
inline void out(T x)
{
	if(x<0) x=-x,putchar('-');
	char ch[20];
	int num(0);
	while(x||!num) ch[++num]=x%10+'0',x/=10;
	while(num) putchar(ch[num--]);
//	putchar(' ');
}
const int N=1e5+79;
int n,m;
struct graph{
	int head[N],next[N<<1],ver[N<<1],tot;
	inline void add(int a,int b)
	{
		ver[++tot]=b;
		next[tot]=head[a];
		head[a]=tot;
	}
}G;
int dis[N];
inline int max(int a,int b){
	return a>b?a:b;
}
inline int min(int a,int b){
	return a>b?b:a;
}
int cnt,k,t;
inline void dfs(int u,int fa,int limit)
{
	int mx(0),mi(N*2);
	for(register int i(G.head[u]);i;i=G.next[i])
	{
		int v(G.ver[i]);
		if(v==fa) continue;
		dfs(v,u,limit);
	    mx=max(dis[v]+1,mx);
		mi=min(dis[v]+1,mi);   	
	}
	dis[u]= mi+mx <0 ? mi : mx;
	if(dis[u]>=limit) dis[u]=-limit-1,++cnt;
}
int main()
{
	read(n);read(k);read(t);
	int u,v;
	rep(i,2,n)
	{
		read(u);read(v);
		G.add(u,v);
		G.add(v,u);
	}
	dfs(1,-1,k);
	out(cnt);
	return 0;
}
2020/11/10 10:20
加载中...