HDU 4897 Little Devil I (树链剖分,好题)

给出一棵树,开始时树的每条边都是白色,接下来q个操作:

1. 将树链u-v上的边翻转(白色变成黑色,黑色变成白色)

2. 将树链u-v上的相邻边翻转(相邻边:有且只有一个点在树链u-v上的边)

3. 询问树链u-v上黑色点的个数。

这题需要对树链剖分有很透彻的理解才能做,对于第一个操作很容就能实现,仔细讲讲第二个操作。

对于第二个操作,不妨先思考下最暴力的方法,就是记录哪些边和剖分后的树链有一个交点,在更新时将这些边翻转。显然这样做时间是不允许的,不妨思考如何优化这步,树链剖分后会有一些特殊的性质:1. 任何两段树链中间一定是被一个轻链连接的,而且任何一段树链一定只有一条轻边;2. 任何一段重链上面连接的必定只有轻链;

通过这我们可以这样更新:用w和l两棵线段树来维护,w维护的是树链黑色点的个数(其中重链上的黑色点个数是真实的,轻链上的还需要后续处理),l维护的是树链上的邻边是否需要翻转;那么在第一个操作时,直接对w线段树操作即可,第二个操作时,要处理三个东西:1. 将对应树链打上是否邻边需要翻转的标记tag2;2. 将每段树链的端点的“重边”翻转(用w线段树做单点更新);3. 对于每段树链经过的“轻链”翻转(同2一样)。当询问时,重链上的结果直接累加,轻链上的结果要和轻链的父亲的tag2异或(因为轻链只有一条,所以考虑单点询问,并且询问父亲的tag2,这样就能判断是此轻链的翻转情况)。

提供一组数据:
2
18
1 2
1 3
1 4
1 9
3 8
4 7
9 6
6 10
10 15
15 16
16 17
9 11
11 12
9 5
5 13
13 14
13 18
9
1 1 17
1 5 14
2 1 17
3 9 5
3 6 5
3 10 5
3 15 5
2 5 14
3 6 18
18
1 2
1 3
1 4
1 9
3 8
4 7
9 6
6 10
10 15
15 16
16 17
9 11
11 12
9 5
5 13
13 14
13 18
3
2 1 17
2 5 11
3 13 12

仔细理解这个过程会发现对树链剖分有更深的理解。

 

LEAVE A COMMENT