[CF1039D]You Are Given a Tree
题目大意:
给定一棵\(n(n\le10^5)\)个节点的树。对于每一个正整数\(k(1\le k\le n)\),求最多能找出多少条包含\(k\)个点的路径,使得这些路径没有公共点。
思路:
答案只可能有大约\(2\sqrt n\)种,对于每一种答案二分其对应的\(k\)的范围,每次自底向上贪心地选择路径。卡卡常就可以过了。
时间复杂度\(\mathcal O(n\sqrt n\log n)\)。
源代码:
#include<cmath>
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=1e5+1;
std::vector<int> e[N];
inline void add_edge(const int &u,const int &v) {
e[u].push_back(v);
e[v].push_back(u);
}
int ans,k,f[N],last[N],tmp[N],dfn[N],id[N];
void dfs(const int &x,const int &par) {
id[dfn[x]=++dfn[0]]=x;
for(unsigned i=0;i<e[x].size();i++) {
const int &y=e[x][i];
if(y==par) continue;
dfs(y,x);
}
}
inline int solve(const int &l) {
if(tmp[l]!=-1) return tmp[l];
k=l;
ans=0;
for(register int i=dfn[0];i>=1;i--) {
const int &x=id[i];
f[x]=1;
int max[2]={0,0};
for(auto &y:e[x]) {
if(dfn[y]<dfn[x]) continue;
f[x]=std::max(f[x],f[y]+1);
int tmp=f[y];
for(register int i=0;i<2;i++) {
if(tmp>max[i]) {
std::swap(tmp,max[i]);
}
}
}
if(max[0]+max[1]+1>=k) {
ans++;
f[x]=0;
}
}
tmp[l]=ans;
last[ans]=std::max(last[ans],l);
return ans;
}
int main() {
const int n=getint();
std::fill(&tmp[1],&tmp[n]+1,-1);
for(register int i=1;i<n;i++) {
add_edge(getint(),getint());
}
dfs(1,0);
const int m=sqrt(n);
for(register int i=1;i<=m;i++) {
printf("%d\n",solve(i));
}
for(register int i=m+1;i<=n;) {
const int ans=solve(i);
int l=last[ans]+1,r=n;
while(l<=r) {
const int mid=(l+r)>>1;
if(solve(mid)==ans) {
l=mid+1;
} else {
r=mid-1;
}
}
for(;i<l;i++) printf("%d\n",ans);
}
return 0;
}