首先对于操作一，我们按照老套路把树上结点用dfs序变成序列，每个结点的子树均为in[x]~out[x]连续的一段，段修改即可。对于操作2，往上找父亲肯定不好实现，怎么办呢？我们只改这一个点，把他改为0，然后在询问x点的时候，我们查询x的子树中是否有0，有的话他一定也是0（他一定是那个点的父亲）。这样就很巧妙的把一个点会影响他的所有祖先转化成了单点修改，查询子树。需要注意的是，这样做的话，做操作1时要检查一下x的子树是否有0，如果有的话，我们不仅要把x的子树都变成1，还要把0这个标记传递给x的父亲，他们还是没有水的。首先对于操作一，我们按照老套路把树上结点用dfs序变成序列，每个结点的子树均为in[x
阅读背景：
CF343D Water Tree（线段树+dfs序+思路）
来源：互联网
分享到：
