设计网站公司都选亿企邦,wordpress跳转安装,湖南网红网站建设有限公司,怎么查网站制作空间有效期CF1017G The Tree 给定一棵树#xff0c;维护以下 \(3\) 个操作#xff1a; 1 x 如果节点 \(x\) 为白色#xff0c;则将其染黑。否则对这个节点的所有儿子递归进行相同操作2 x 将以节点 \(x\) 为根的子树染白。3 x 查询节点 \(x\) 的颜色 \(n,q\le 10^5\)。 \(\bigstar\text… CF1017G The Tree 给定一棵树维护以下 \(3\) 个操作 1 x 如果节点 \(x\) 为白色则将其染黑。否则对这个节点的所有儿子递归进行相同操作2 x 将以节点 \(x\) 为根的子树染白。3 x 查询节点 \(x\) 的颜色 \(n,q\le 10^5\)。 \(\bigstar\texttt{Hint-1}\)如果真的向题目所说的去给每个点染色将非常难维护。如果发现题目中信息混乱不妨向统计学方向考虑我们记下这个 \(x\) 向下多少深度被染色在每个点上根据它与根的路径查询答案。 如果没有 \(2\) 操作我们在每个点上记录在它身上加了几次那么查询时询问根到它的路径是否存在一段后缀和等于这段后缀的长度。不妨用一个更优美的解决方法将每个点初始值设为 \(-1\)那么查询是否有一段后缀和 \(\ge 0\)。 \(\bigstar\texttt{Hint-2}\)那么 \(2\) 操作呢继续利用统计学将 \(x\) 的权值赋为 \(x\) 到根节点的权值加一。 另一种操作是离线后处理但比较麻烦。 咕咕咕
