『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;
}
<后记>
最新文章
- iOS应用中的相关正则及验证
- Java 数据库操作类
- 实现iOS图片等资源文件的热更新化(一): 从Images.xcassets导出合适的图片
- asp.net中控制反转的理解
- Java虚拟机内存管理原理基础入门
- UOJ265 【NOIP2016】愤怒的小鸟
- 几个Windows电脑小技巧
- jQuery延迟加载(懒加载)插件 – jquery.lazyload.js
- Spring 文章推荐
- js图片时间翻转
- ubuntu 安装编译nginx,并实现HLS推送,,可以实现摄像头直播
- [HDOJ5583]Kingdom of Black and White(暴力)
- mvc 笔记
- centos7安装nginx必要环境
- jQuery插件之-----弹性运动
- JS实现日期选择
- Laravel 5.6: Specified key was too long error
- Django-rest-framework 接口实现 ModelSerializer 使用
- Flutter之 LimitedBox、Offstage、OverflowBox、SizedBox详解
- jQuer插件满屏气泡飘落动画效果
热门文章
- CTF必备技能丨Linux Pwn入门教程——PIE与bypass思路
- 如何在unbuntu 16.04上离线部署openssh
- 当请求进入Nginx后,每个HTTP执行阶段的作用
- Rocketmq原理&;最佳实践
- SQLAlchemy(3)
- http中get,post,put,delete方法的用法以及区别
- python27期尚哥讲并发编程:
- echars 饼状图 轮循 水平翻转
- Flask-Login中装饰器@login_manager.user_loader的作用及原理
- mysql悲观锁的实现