把一颗树分为多条长度为k的不交路径,求k 从1~n的最多条数
因为一个节点最多被使用一次,叶子只有一条被覆盖的情况(从父亲来),所以我们可以贪心的从叶子向上走,长度一到k就断掉。这样的贪心是正确的
可以发现,随着k的递增,答案是下降的。因此我们可以发现相同的答案都是成段的。我们可以想到二分,答案最多n种,最多二分n次,时间复杂度为\(O(n^2 \ log \ n)\)
但是我们可以发现一棵n个节点树最多可以被分为n/k条,有点像整除分块。可以证明答案最多有\(\sqrt n\)段
所以实际的时间复杂度为\(O(n \ \sqrt n \ log \ n)\)
但是实际上还可以优化,我们可以将k<=T的直接暴力。如果二分的话,可能会更劣,因为可能会多个log ,大于k的二分,可以做到\(O(n \ log \ n \ \frac{n}{T} )\),可以发现T取\(\sqrt{n \ log \ n}\)可以使得前面的暴力和后面的二分的时间复杂度和的最小(基本不懂式)。
const int N = 1e5 + 79;
struct graph {
int head[N], tot, next[N << 1], ver[N << 1];
inline void add(int a, int b) {
ver[++tot] = b;
next[tot] = head[a];
head[a] = tot;
}
} G;
int n, block;
int fa[N], b[N], tim;
int len[N];
inline void dfs(int x) {
repg(x) {
int y(G.ver[i]);
if(y == fa[x]) continue;
fa[y] = x;
dfs(y);
}
b[++tim] = x;
}
inline int calc(int k) {
int res(0);
rep(i, 1, n) {
len[i] = 1;
}
rep(i, 1, n) {
int x = b[i];
if(fa[x] && len[x] != -1 && len[fa[x]] != -1) {
if(len[x] + len[fa[x]] >= k) {
len[fa[x]] = -1;
++res;
} else {
len[fa[x]] = max(len[fa[x]], len[x] + 1);
}
}
}
return res;
}
int ans[N];
int main() {
read(n);
int x, y;
rep(i, 2, n) {
read(x);
read(y);
G.add(x, y);
G.add(y, x);
}
block =sqrt(n * log2(n));
dfs(1);
out(n, '\n');
rep(i, 2, block) {
out(calc(i), '\n');
}
int l, r, ans, t;
for(int i = block + 1; i <= n; i = l + 1) {
l = i;
r = n;
ans = calc(i), t = i;
while(l <= r) {
int mid(l + r >> 1);
if(calc(mid) == ans) {
l = mid + 1;
t = mid;
} else r = mid - 1;
}
rep(k, i, t) {
out(ans, '\n');
}
l = t;
}
return 0;
}