codeforces 1003E Tree Constructing

codeforces 1003E Tree Constructing

​​ 考虑如何构造这棵树我们只需要把直径先构造出来然后在直径上长毛即可

那么每个直径上的点保证他的深度不超过到直径两端距离的最小值即可

注意特判一些k=1或者k=2的小数据

#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) {x=x*10+ch-'0',ch=gc();} return x*f;}const int N=4e5+10;struct node{ int x,y;};vector a;int n,D,k,d[N],now,maxd,lt;inline void dfs(int x,int dep){ if (dep>maxd) return; if (x>n) return;vector pd; while(d[x]&<) pd.push_back(now),--lt,a.push_back((node){x,now}), --d[now],++now,--d[x]; for (int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。