rockdu
A tree is an undirected graph with exactly one simple path between each pair of vertices. We call a set of simple paths kk-valid if each vertex of the tree belongs to no more than one of these paths (including endpoints) and each path consists of exactly kk vertices.
You are given a tree with nn vertices. For each kk from 11 to nn inclusive find what is the maximum possible size of a kk-valid set of simple paths.
The first line of the input contains a single integer nn (2≤n≤1000002≤n≤100000) — the number of vertices in the tree.
Then following n−1n−1 lines describe the tree, each of them contains two integers vv, uu (1≤v,u≤n1≤v,u≤n) — endpoints of the corresponding edge.
It is guaranteed, that the given graph is a tree.
Output nn numbers, the ii-th of which is the maximum possible number of paths in an ii-valid set of paths.
7 1 2 2 3 3 4 4 5 5 6 6 7
7 3 2 1 1 1 1
6 1 2 2 3 2 4 1 5 5 6
6 2 2 1 1 0
One way to achieve the optimal number of paths for the second sample is illustrated in the following picture:
题意：给你一棵树，问用长度为k的链去覆盖它，链两两不能相交，最多能盖多少条链上去。
我们从简单的情况考虑，在一条链上对于每一个k答案会是n/k。并且我们注意到n/k的整出性质：只有sqrt(n)种取值，并且答案单调。我们大胆猜想，树上情况的取值也在sqrt(n)级别内，显然也是单调的。
如果我们可以对于k单点求值那么我们就可以记忆化+二分在sqrt(n)log(n)的额外复杂度下解决本题，那么问题在于如何对于k单点求值。
考虑贪心，每一次我们枚举最高点在u的链的放置方案，这样链的两端一定插在不同的儿子中。我们发现每一个儿子对父亲的贡献只有向下到达的最深点，因为任意两条链不能重叠。那么每一次找寻儿子中最深的两个，如果大于k那么就放置，否则更新当前u的最深处。总复杂度：O(n sqrt(n)log(n))
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e5 + 5;
struct edge {
int v, next;
} e[maxn << 1];
int head[maxn], cnt, depth[maxn], dfn[maxn], dcnt, ans, fa[maxn];
int n, u, v, mem[maxn], _1st[maxn], _2nd[maxn], ord[maxn], B = 500;
void adde(const int &u, const int &v) {
e[++cnt] = (edge) {v, head[u]};
head[u] = cnt;
}
void dfs(const int &u, const int &p) {
fa[u] = p;
dfn[u] = ++dcnt;
ord[dcnt] = u;
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(v == p) continue;
dfs(v, u);
}
}
int Calc(const int &k) {
int p, u, ans = 0;
memset(_1st, 0, sizeof(_1st));
memset(_2nd, 0, sizeof(_2nd));
for(register int i = n; i >= 1; --i) {
u = ord[i], p = fa[u];
if(!_1st[u]) depth[u] = 1;
if(_2nd[u] + _1st[u] + 1 >= k) ++ans, depth[u] = 0;
else depth[u] = _1st[u] + 1;
if(depth[u] > _1st[p]) _2nd[p] = _1st[p], _1st[p] = depth[u];
else if(depth[u] > _2nd[p]) _2nd[p] = depth[u];
}
return ans;
}
int DF(int l, int r, int ans) {
while(l < r - 1) {
int mid = l + r >> 1;
if(mem[mid] == -1)
mem[mid] = Calc(mid);
if(mem[mid] >= ans) l = mid;
else r = mid;
}
return l;
}
int main() {
memset(mem, -1, sizeof(mem));
scanf("%d", &n);
for(register int i = 1; i < n; ++i)
scanf("%d%d", &u, &v), adde(u, v), adde(v, u);
dfs(1, 0), mem[1] = n, B = min(B, n);
for(register int i = 2; i <= B; ++i)
mem[i] = Calc(i);
for(register int l = B + 1, r; l <= n; l = r + 1) {
if(mem[l] == -1) mem[l] = Calc(l);
r = DF(l, n + 1, mem[l]);
for(register int i = l + 1; i <= r; ++i)
mem[i] = mem[l];
}
for(register int i = 1; i <= n; ++i)
printf("%d\n", mem[i]);
return 0;
}
没有帐号? 立即注册