xjoi 模拟赛 树剖

题意:

给定一颗树,

有两个操作

u->v 所有边^

u->v 所有不在路径上的边,但是与路径上的点有连接的边^

询问给定u,v

求染色的边数

题解

我们需要维护两个不同的线段树,分别对应两种操作

对于第一个操作

也就是裸的树剖

我们把一条边的权值赋在深度较大的点上

那么边权和点权的处理就一样了

对于第二个操作

那么处理就比较的特殊了

首先你要发现一个性质

对于二操作 其实他等同于对路径上的点染色

询问的时候对于每一条边,那么就是看这条边的两个端点是否是相同的颜色

xor一下就行了

那么对于查询来说

也就是如果在重链上,也就是普通的查询

对于轻边的点 将1号操作和2号操作xor一下就行了

于是这题就好了,只不过有些丧心病狂

发表评论

电子邮件地址不会被公开。 必填项已用*标注