『You Are Given a Tree 整体分治 树形dp』

<更新提示>

<第一次更新>

---

<正文>

You Are Given a Tree

Description

A tree is an undirected graph with exactly one simple path between each pair of vertices. We call a set of simple paths k -valid if each vertex of the tree belongs to no more than one of these paths (including endpoints) and each path consists of exactly k vertices.

You are given a tree with nn vertices. For each k from 1 to nn inclusive find what is the maximum possible size of a k -valid set of simple paths.

Input Format

The first line of the input contains a single integer n ( 2≤n≤100000 ) — the number of vertices in the tree.

Then following n - 1 lines describe the tree, each of them contains two integers v , u ( 1≤v,u≤n ) — endpoints of the corresponding edge.

It is guaranteed, that the given graph is a tree.

Output Format

Output n numbers, the i -th of which is the maximum possible number of paths in an i -valid set of paths.

Sample Input

7
1 2
2 3
3 4
4 5
5 6
6 7

Sample Output

7
3
2
1
1
1
1

解析

可以先考虑\(k\)确定时的做法，不妨进行树形\(dp\)。\(f[x]\)代表以\(x\)为根的子树中最长链的长度，同时维护一下全局答案。转移方式就是能合并就合并，反之选一条最长的链向上延伸，时间复杂度\(O(n)\)。

我们发现\(k\le\sqrt n\)时答案最多只有\(\sqrt n\)种取值，\(k>\sqrt n\)时答案\(\leq\sqrt n\)，也只有\(\sqrt n\)种取值，并且答案的大小具有单调性，于是就有一个很直观的想法，二分找到段边界，统一每一段的答案即可，时间复杂度\(O(n\sqrt n\log_2n)\)。

但是直接这样写常数可能比较大，换一种整体二分的写法常数更小一些，时间复杂度不变，就可以通过本题了。

\(Code:\)

#include <bits/stdc++.h>
using namespace std;
const int N = 100020;
struct edge { int ver,next; } e[N*2];
int n,t,Head[N],f[N],cnt,ans[N];
inline void insert(int x,int y) { e[++t] = (edge){y,Head[x]} , Head[x] = t; }
inline void input(void)
{
    scanf("%d",&n);
    for (int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        insert( x , y );
        insert( y , x );
    }
}
inline void dp(int x,int fa,int len)
{
    int Max = 0 , sec = 0;
    for (int i=Head[x];i;i=e[i].next)
    {
        int y = e[i].ver;
        if ( y == fa ) continue;
        dp( y , x , len );
        if ( f[y] >= Max ) sec = Max , Max = f[y];
        else if ( f[y] > sec ) sec = f[y];
    }
    if ( sec + Max + 1 >= len ) f[x] = 0 , cnt++;
    else f[x] = Max + 1;
}
inline void divide(int st,int ed,int l,int r)
{
    if ( st > ed || l > r ) return;
    if ( l == r )
    {
        for (int i=st;i<=ed;i++) ans[i] = l;
        return;
    }
    int mid = st + ed >> 1; cnt = 0;
    dp( 1 , 0 , mid );
    ans[mid] = cnt;
    divide( st , mid-1 , cnt , r );
    divide( mid+1 , ed , l , cnt );
}
int main(void)
{
    input();
    divide( 1 , n , 0 , n );
    for (int i=1;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}

---

<后记>