【杂题】[CodeForces 1172E] Nauuo and ODT【LCT】【口胡】
Description
给出一棵n个节点的树,每个点有一个1~n的颜色
有m次操作,每次操作修改一个点的颜色
需要在每次操作后回答树上\(n^2\)条路径每条路径经过的颜色种类数和。
\(n,m<=400000\)
Solution
挺有意思的一个套路
首先我们单独计算每种颜色的贡献,对于每种颜色的点集分开考虑,我们需要计算至少经过了其中一个点的路径条数。
正难则反,考虑计算一个点都没经过的路径条数,那就是将点集删去后剩余连通块的大小平方和。
考虑这样一个模型
对于原本每种颜色有一个黑白两色的树,需要支持在某棵树上颜色翻转,求白连通块的大小平方和。
黑点总个数为n
如果只有一棵树,那很好办,直接用个LCT维护白连通块,对于每个点开个虚点连儿子即可。
但这里白点总个数是\(O(n^2)\)的
原题解给出了这样一个精妙的做法。(翻译一遍题解)
先定一个树根
我们维护所有的黑连通块,每个黑连通块深度最浅的点的父亲记为这个连通块的顶点,(对于树根我们也开一个0号节点),显然顶点一定是白的。
LCT的时候,我们将顶点相同的所有节点看做在一个连通块内,事实上他们不一定连通。
现在对于每个节点都记录两个值,一个是连通块中的子树大小,一个是所有儿子的子树大小的平方和。
答案显然就是所有顶点的第二个值的和。
这样颜色反转时,我们只需要讨论这个点是黑点还是白点,黑点的话就cut父亲,显然这个点的信息不变,但这个点会成为顶点,因此更新答案。
白点的话就link父亲,此时父亲变成顶点,这个点的信息还是没变,只用修改父亲节点的值。
我们对于每种颜色都按照操作的时间顺序跑一遍,由于总操作数是\(O(m)\)的,因此总共需要用到的点数是\(O(n+m)\)的
我还没去写这道题,感觉具体可以把每种颜色操作一遍,然后回撤到下一种颜色的初始状态,这样总的操作次数仍然是\(O(n+m)\)的。
总的时间复杂度\(O((n+m)\log n)\)
最新文章
- iOS JavaScriptCore与H5交互时出现异常提示
- C语言回顾-结构体、枚举和文件
- Linq to entities 学习笔记
- JS在火狐浏览器下如何关闭标签?
- 操作properties文件,注意抹掉最前面的";file:";
- 20151124002 treeView 数型菜单的操作
- gomoblie flappy 源码分析:图片素材和大小的处理
- iis实现类似tomcat ip:port直接访问站点
- HTTP使用BASIC认证的原理及实现方法
- Linux makefile教程之使用变量五[转]
- js观察者模式
- 利用Php ssh2扩展实现svn自动提交到测试服务器
- python- 迭代器与生成器
- Swift语言Storyboard教程:第一部分
- ionic3.0--angular4.0 引入第三方插件库的方法
- jenkin插件整理
- DSAPI 图形图像篇(上)
- mobile deeplearning
- SQL 数据库开发一些精典的代码(转永南)
- python科学计算模块NumPy
热门文章
- oracle数据段详解
- TCP/IP 物理层卷四 -- 数据报与虚电路
- Jconsole与Jmx 分析JVM状况(上) 转
- Linux(17):Shell编程(4)
- Charles学习(二)之使用Map local代理本地静态资源以及配置网页代理在Mac浏览器上调试移动端
- laravel 5.7 引入Illuminate\Http\Request 在类内调用 Request 提示不存在的问题
- Centos7:JDK1.8环境配置
- java中的Enum在@RestController(@ResponseBody) 注解下返回的表现
- python视频学习笔记4(函数)
- dumpe2fs Linux支持的文件系统