网站服务器 试用,国家企业信用公示信息查询平台,wordpress批量导入,音响网站模板免费下载cf1039D 链接 cf 思路 一次k可以贪心O(n)算。 对于\(≤\sqrt{n}\)的k#xff0c;暴力算。 对于\(#xff1e;\sqrt{n}\)的k#xff0c;最多会有\(\sqrt{n}\)种答案#xff0c;而且答案单调。 二分就行了。 复杂度\(O(nlognn\sqrt{n}logn)\) 递归会被卡#xff0c;所以要记… cf1039D 链接 cf 思路 一次k可以贪心O(n)算。 对于\(≤\sqrt{n}\)的k暴力算。 对于\(\sqrt{n}\)的k最多会有\(\sqrt{n}\)种答案而且答案单调。 二分就行了。 复杂度\(O(nlognn\sqrt{n}logn)\) 递归会被卡所以要记录dfs序然后循环 代码 #include cstdio
#include iostream
#include cmath
using namespace std;
const int _1e57;
inline int read() {int x0,f1;char sgetchar();for(;s9||s0;sgetchar()) if(s-) f-1;for(;s0s9;sgetchar()) xx*10s-0;return x*f;
}
int n,g[_],head[_],tot,stak[_],fa[_],top;
struct node {int v,nxt;}e[_1];
inline void add(int u,int v) {e[tot].vv,e[tot].nxthead[u],head[u]tot;}
void dfs(int u,int F) {fa[u]F,stak[top]u;for(int ihead[u];i;ie[i].nxt)if(e[i].v!F) dfs(e[i].v,u);
}
int calc(int L) {int ans0;for(int i1;in;i) g[i]1;for(int in;i2;--i) {int ustak[i],vfa[u];if (g[v]g[u]L) ans,g[v]0;else if(g[v]) g[v]max(g[v],g[u]1);}return ans;
}
int main() {nread();for(int i1,u,v;in;i) {uread(),vread();add(u,v),add(v,u);}int ksqrt(n*log2(n));printf(%d\n,n);dfs(1,0);for(int i2;ik;i) printf(%d\n,calc(i));for(int ik1;in;) {int li,rn,Ri,anscalc(i);while(lr) {int mid(lr)1;if(calc(mid)ans) Rmid,lmid1;else rmid-1;}for(;iR;i) printf(%d\n,ans);}return 0;
} 转载于:https://www.cnblogs.com/dsrdsr/p/11405978.html
