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

2023-12-19 08:29:51

<更新提示>

<第一次更新>

<正文>

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

Sample Output

解析

可以先考虑\(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;

}

<后记>

码农公寓