[CF1009F] Dominant Indices (+dsu on tree详解)
2024-09-07 06:56:42
这道题用到了dsu(Disjoint Set Union) on tree,树上启发式合并。
先看了CF的官方英文题解,又看了看zwz大佬的题解,差不多理解了dsu on tree的算法。
但是时间复杂度有点玄学,问了一下zwz大佬才懂了为什么是nlogn。
先考虑暴力n^2的算法。
显然对于某个点,搜一遍它的子树,就能得到这个点的答案。这一步是O(n)的。
每个点都这么搞一遍,就是O(n^2)的暴力做法。
但是这个暴力做法有一点不足,子节点的答案没有应用到父节点的计算中,白白浪费时间重算一遍。
考虑优化,类似树链剖分,找出子树最大的儿子称作重儿子,把它的答案留着,这样计算父节点时就不用搜这个重儿子了。
显然保留子树最大的儿子的信息,能够节约最多的时间。
但是如果计算完重儿子的答案,保留了信息,再计算别的儿子的答案,已保留的信息会对当前的计算产生干扰。
所以我们先计算轻儿子,最后计算重儿子。
如果是轻儿子,更新答案计算后,暴力再改回去。
如果是重儿子,就留着。
计算完所有儿子的答案后,最后计算当前点。
只需要加上轻儿子的信息就好。重儿子的信息已经留着了,不用再加了。
下面是zwz大佬对于dsu on tree时间复杂度的证明:
每个节点只会在祖先节点的计算中被搜到。
而且只有它到它父亲是轻边的时候才会搜一遍。
所以每个点的计算次数是它到根的轻边数量,为logn。
所以总时间复杂度是nlogn。
感觉dsu也是挺暴力的,每次留一个,居然时间上优化了很多。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 1000005
using namespace std; int n;
int hd[MAXN],nx[MAXN<<],to[MAXN<<],ec;
int dep[MAXN],sz[MAXN],ans[MAXN],cnt[MAXN]; void edge(int af,int at)
{
to[++ec]=at;
nx[ec]=hd[af];
hd[af]=ec;
} void pre(int p,int fa)
{
sz[p]=;
dep[p]=dep[fa]+;
for(int i=hd[p];i;i=nx[i])
{
if(to[i]==fa)continue;
pre(to[i],p);
sz[p]+=sz[to[i]];
}
} struct data
{
int d,v;
friend bool operator<(data q,data w)
{
if(q.v==w.v)return q.d>w.d;
return q.v<w.v;
}
}; priority_queue<data>qq; void add(int p,int fa)
{
cnt[dep[p]]++;
data neo={dep[p],cnt[dep[p]]};
qq.push(neo);
for(int i=hd[p];i;i=nx[i])if(to[i]!=fa)add(to[i],p);
} void del(int p,int fa)
{
cnt[dep[p]]--;
for(int i=hd[p];i;i=nx[i])if(to[i]!=fa)del(to[i],p);
} void dfs(int p,int fa,int stay)
{
int son=,mx=-;
for(int i=hd[p];i;i=nx[i])
{
if(to[i]==fa)continue;
if(mx<sz[to[i]])mx=sz[to[i]],son=to[i];
}
for(int i=hd[p];i;i=nx[i])
{
if(to[i]==fa||to[i]==son)continue;
dfs(to[i],p,);
}
if(son)dfs(son,p,);
for(int i=hd[p];i;i=nx[i])
{
if(to[i]==fa||to[i]==son)continue;
add(to[i],p);
}
cnt[dep[p]]++;
data neo={dep[p],cnt[dep[p]]};
qq.push(neo);
ans[p]=qq.top().d-dep[p];
if(!stay)
{
del(p,fa);
while(!qq.empty())qq.pop();
}
} int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
edge(x,y);
edge(y,x);
}
pre(,);
dfs(,,);
for(int i=;i<=n;i++)printf("%d\n",ans[i]);
return ;
}
CF1009F Dominant Indices
P.S. 调试的时候改小了数组,提交的时候忘改回去了......改回去之后直接A掉了......有点桑心哈哈哈
最新文章
- 使用TextUtils.isEmpty简单化代码
- Android——播放器和图片轮播
- wordpress 开发日志及技巧收集
- HDU-2262 Where is the canteen 概率DP,高斯消元
- js apply 和call的区别
- javamail发送邮件的简单实例(转)
- Linux下php+mysql+nginx编译搭建(一)
- imagebutton、imageview的属性
- 2.1. 托管对象模型是什么(Core Data 应用程序实践指南)
- InfluxDB读写性能测试
- jenkins 解决构建成功后进程消失的问题
- DGTween 控制物体移动并且播放相应的动画
- python 全栈开发笔记 2
- pythonの信号量
- 29.Mysql监控
- C# 后台获取前台交互判断
- Gym-101375C MaratonIME eats japanese food 初始化struct技巧
- node.js express 4.x 安装指南 (找了很久呀,痛苦之路)
- PAT 1073 多选题常见计分法(20)(代码+思路)
- js模态窗口返回值(table)
热门文章
- python 手动安装模块
- TiKV 在京东云对象存储元数据管理的实践
- flutter依赖某些插件,点击运行会出现错误
- Gradle project sync failed. Please fix your project and try again
- PAT Basic 插⼊与归并(25) [two pointers]
- UML-如何创建领域模型?
- Maven--仓库的分类
- C++类的访问控制关键字
- 进程间数据共享 (multiprocess.Manager)
- SQL Server Driver for PHP之sqlsrv相关函数