1. 用途

首先是有根树。
我们需要实现如从点u到点v的(最短)路径上所有点的权值+1这种操作。
而且我们不需要频繁的求某个点的权值。

2. 实现方法

类似于前缀和的思想。
首先我们定义:val[i]表示点i的标记,cal[i]表示点i的权值,lca(i,j)表示点i与点j的最近公共祖先,fa[i]表示点i的父亲节点(等于0表示没有父亲节点)。

先看操作:
点u到点v之间的路径上每个点的权值+1:

求点a的权值:

注意cal[i]并不是时时刻刻一定等于点i的权值,而是你calc(i)后才一定是正确的值。

上面的操作为什么是这样的呢?首先不难发现cal[a]就是a所有的儿子节点和a的val的和,因为其实val[i]++等价于将点i到根节点的所有点的权值都加了1,所以change函数中先将val[u]++,val[v]++,这样lca(u,v)的权值本应该只加1,现在却加了两次,所以val[lca(u,v)]--。而fa[lca(u,v)]本来权值不应增加,而此时权值却加了2,所以应该减去2,但是因为lca(u,v)的权值已经减一了,所以val[fa[lca(u,v)]]只需要减一即可。

这样就实现了O(1)的修改,O(n)的查询所有节点的权值了。