search

OkazakiYumemi / okazakiyumemi.github.io

Maybe just a blog
https://okazakiyumemi.github.io/
0 stars 0 forks source link

「CF1442E」Black, White and Grey Tree | Okazaki Yumemi's blog #139

Open OkazakiYumemi opened 4 years ago

OkazakiYumemi commented 4 years ago

https://okazakiyumemi.github.io/blog/CF1442E/

题意简述给一棵树，树上每个节点都为灰色、白色或黑色。每次可以选择一个连通块中的一个节点集合，要求集合中不能同时存在黑色和白色的节点，然后删去集合中所有节点。问最少多少次可以把整棵树删完。 $n\le 200000$。

Owen608 commented 4 years ago

为啥灰色的点可以钦定祖先的颜色 QAQ

OkazakiYumemi commented 3 years ago

@Owen608

为啥灰色的点可以钦定祖先的颜色 QAQ

因为讨论一下可以发现，钦定为最近非灰色祖先的颜色不会增加直径的长度

Owen608 commented 3 years ago

@OkazakiYumemi

@Owen608

为啥灰色的点可以钦定祖先的颜色 QAQ

因为讨论一下可以发现，钦定为最近非灰色祖先的颜色不会增加直径的长度

对哦，我傻了